qiuP7150玄关
  • 板块灌水区
  • 楼主oier25
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/1 15:27
  • 上次更新2024/8/1 16:11:20
查看原帖
qiuP7150玄关
719233
oier25楼主2024/8/1 15:27
#include<bits/stdc++.h>
#define int long long
using namespace std;
int N,to[2005],nxt[2005],h[2005],cnt,ns,es,zr[2005];
bool vis[2005];
struct node{
	int x,y,bian;
	int dy;
	bool f;
	node(){
		dy=1e9+5;
	}
}n[2005],e[2005];
bool cmp1(node u,node v){
	return (u.x<v.x);
}
bool cmp2(node u,node v){
	return (u.y<v.y);
}
void add(int u,int v){
	to[++cnt]=v;
	nxt[cnt]=h[u];
	h[u]=cnt;
}
void dfs(int u){
	vis[u]=1;
	for(int e=h[u];e;e=nxt[e]){
		int v=to[e];
//		cout<<"u="<<u<<"v="<<v<<"\n";
		dfs(v);
		zr[u]+=zr[v]+1;
	}
	return ;
}
signed main(){
//	freopen("rut.in","r",stdin);
//	freopen("rut.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>N;
	for(int i=1;i<=N;i++){
		char c;
		cin>>c;
		if(c=='N'){
			cin>>n[++ns].x;
			cin>>n[ns].y;
			n[ns].bian=i;
		}
		else {
			cin>>e[++es].x;
			cin>>e[es].y;
			e[es].bian=i;
		}
	}
	sort(n+1,n+ns+1,cmp1);
	sort(e+1,e+es+1,cmp2);
	for(int j=1;j<=es;j++){
		int x=e[j].x,y=e[j].y;
		for(int i=1;i<=ns;i++){
			int x2=n[i].x,y2=n[i].y;
			if(x2<x||y<y2||x2+y2==x+y||n[i].dy<y||n[i].f)continue;
//			cout<<x<<"=x x2="<<x2<<"\n";
//			cout<<y<<"=y y2="<<y2<<"\n";
//			cout<<"j="<<e[j].bian<<" i="<<n[i].bian<<"\n";
			if(x2-x>y-y2){
				add(n[i].bian,e[j].bian);
//				cout<<"114514\n";
				break;
			}
			else {
				n[i].dy=y;
				n[i].f=1;
				add(e[j].bian,n[i].bian);
//				cout<<"1919810\n";
			}
		}
	}
	for(int i=1;i<=N;i++){
		if(!vis[i])dfs(i);
	}
//	if(N==6)cout<<"0\n0\n1\n2\n1\n0\n";
	for(int i=1;i<=N;i++){
		cout<<zr[i]<<"\n";
	}
	return 0;
}

/*
5
E 0 5
N 2 0
E 3 7
N 4 1
N 1 2
*/

只过样例

10分 Help 急

2024/8/1 15:27
加载中...