社区讨论

70分求助

P8252 [NOI Online 2022 提高组] 讨论参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo8l7v6s
此快照首次捕获于
2023/10/27 20:26
2 年前
此快照最后确认于
2023/10/27 20:26
2 年前
查看原帖
WA于Subtask #1
#12 #17 #20
CPP
#include<bits/stdc++.h>
using namespace std;
const int MA=1000006;
int n,pan=0,cnt[MA],lu[MA];
struct zh{
	int k,x;
}a[MA];
bool pai(zh x,zh y){
	if(x.k!=y.k){
		return x.k>y.k;
	}
	if(x.x!=y.x){
		return x.x<y.x;
	}
}
vector<int>q[MA];
int chuli(int x){
	int kk=a[x].k,zhe=a[x].x;
	for(int i=0;i<kk;i++){
		int j=q[zhe][i];++cnt[lu[j]];
	}
	for(int i=0;i<kk;i++){
		int j=q[zhe][i];int y=lu[j];
		if(cnt[y]<kk&&y!=0){
			printf("YES\n%d %d\n",a[y].x,zhe);
			return 1;
		}
	}
	for(int i=0;i<kk;i++){
		int j=q[zhe][i];cnt[lu[j]]=0;lu[j]=x;
	}
	return 0;
}
void qing(){
	for(int i=0;i<=n;i++){
		q[i].clear();lu[i]=0;
	}
}
int main()
{
	int T;scanf("%d",&T);
	while(T>0){
		--T;scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i].k);a[i].x=i;
			for(int j=1;j<=a[i].k;j++){
				int x;scanf("%d",&x);q[i].push_back(x);
			}
		}
		sort(a+1,a+1+n,pai);pan=0;
		for(int i=1;i<=n;i++){
			if(a[i].k==0){
				continue;
			}
			if(chuli(i)==1){
				pan=1;break;
			}
		}
		if(pan==0){
			printf("NO\n");
		}
		qing();
	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...