90分最后一个点wa求助
查看原帖
90分最后一个点wa求助
237893
donkeys楼主2022/4/3 12:38

https://www.luogu.com.cn/record/73030310

#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
namespace IO
{
	bool EOFstate = 0;
	template<typename T>inline void read(T &x)
	{
		x = 0; int f = 1; char c = getchar();
		while(('0' > c || c > '9') && !EOFstate) { if(c == '-')f = -1; c = getchar(), EOFstate = c == EOF; }
		while('0' <= c && c <= '9')x = (x << 3) + (x << 1) + c - '0', c = getchar();
		x *= f;
	}
	template<typename T = int>inline T read()
	{
		T x;
		x = 0; int f = 1; char c = getchar();
		while(('0' > c || c > '9') && !EOFstate) { if(c == '-')f = -1; c = getchar(), EOFstate = c == EOF; }
		while('0' <= c && c <= '9')x = (x << 3) + (x << 1) + c - '0', c = getchar();
		x *= f;
		return x;
	}
	template<typename T>inline void write(T x, char end = ' ')
	{
		if(x == 0)return putchar('0'), putchar(end), void();
		if(x < 0)putchar('-'), x = -x;
		char c[21], cnt = 0;
		while(x)c[cnt++] = x % 10 + '0', x /= 10;
		while(cnt)putchar(c[--cnt]); putchar(end);
	}
}using namespace IO;
#define N 3000006
int n;
vector<int>can[N], inc[N];
bool used[N];
inline void init()
{
	memset(used, 0, sizeof(used));
	can[n + 1].clear();
	for(int i = 1; i <= n; ++i)
		inc[i].clear(), can[i].clear(), can[n + 1].emplace_back(i), inc[i].emplace_back(n + 1);
}
inline void YES(int a, int b)
{
	puts("YES"), write(a), write(b, '\n');
}
inline void NO()
{
	puts("NO");
}
template<typename Itr, typename Val>
inline bool myfind(Itr begin, Itr end, Val key)
{
	Itr t = lower_bound(begin, end, key);
	return t != end && *t == key;
}
inline bool chk(int f, int s)
{
	for(int i : can[s])
	{
		if(!myfind(can[f].begin(), can[f].end(), i))
			return 0;
	}
	return 1;
}
inline void solve()
{
	read(n);
	init();
	for(int i = 1, k; i <= n; ++i)
	{
		read(k);
		for(int j = 1, t; j <= k; ++j)
			read(t), can[i].emplace_back(t), inc[t].emplace_back(i);
	}//can为每个人会做的题,inc是每个题会做的人
	for(int i = 1; i <= n; ++i)
		sort(can[i].begin(), can[i].end());
	used[n + 1] = 1;//插入一个全集,防止越界
	for(int id = 1; id <= n; ++id)
	{
		stable_sort(inc[id].begin(), inc[id].end(),
					[](int a, int b){ return can[a].size() > can[b].size(); });
		int la;//相当于父亲
		for(int i : inc[id])
		{
			if(used[i]){ la = i; continue; }
			used[i] = 1;
			if(can[i].size() == can[la].size())
			{
				if(can[i] == can[la])//完全相等
					la = i;
				else
					return YES(la, i);
			}
			else
			{
				if(chk(la, i))//是包含关系
					la = i;
				else
					return YES(la, i);
			}
		}
	}
	return NO();
}
int main()
{
	int T = read();
	while(T--)
		solve();
	return 0;
}
2022/4/3 12:38
加载中...