Submission #825276

#	Time	Username	Problem	Language	Result	Execution time	Memory
825276		arnold518	Keys (IOI21_keys)	C++17	100 / 100	913 ms	197744 KiB

keys

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, M;
int R[MAXN+10];
int ans[MAXN+10];

set<pii> adj[MAXN+10];
vector<pii> adj2[MAXN+10];
set<int> S[MAXN+10];

int par[MAXN+10];
int vis[MAXN+10];
bool dead[MAXN+10];

struct UF
{
	int par[MAXN+10];
	int Find(int x)
	{
		if(x==par[x]) return x;
		return par[x]=Find(par[x]);
	}
	void Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		par[x]=y;
	}
	void init()
	{
		for(int i=1; i<=N; i++) par[i]=i;
	}
}uf, uf2;

int cnt[MAXN+10];

vector<int> find_reachable(vector<int> _R, vector<int> _U, vector<int> _V, vector<int> _C)
{
	N=_R.size(); M=_U.size();
	for(int i=1; i<=N; i++) R[i]=_R[i-1]+1;
	for(int i=1; i<=M; i++)
	{
		int u=_U[i-1]+1, v=_V[i-1]+1, w=_C[i-1]+1;
		if(R[u]!=w) adj[u].insert({w, v});
		else adj2[u].push_back({w, v});

		if(R[v]!=w) adj[v].insert({w, u});
		else adj2[v].push_back({w, u});
	}

	uf.init(); uf2.init();
	for(int i=1; i<=N; i++)
	{
		S[i].insert(R[i]);

		if(!adj2[i].empty())
		{
			par[i]=adj2[i].back().second;
			uf.Union(i, par[i]);
		}
	}

	queue<int> Q;
	for(int i=1; i<=N; i++)
	{
		int now=i;
		while(1)
		{
			if(vis[now]) break;
			vis[now]=i;
			if(par[now]==0) break;
			now=par[now];
		}
		if(par[now]!=0 && vis[now]==i) Q.push(now);
	}

	while(!Q.empty())
	{
		int now=Q.front(); Q.pop();
		now=uf2.Find(now);

		vector<int> V;
		for(int i=par[now]; i!=now; i=uf2.Find(par[i])) V.push_back(i);

		for(auto it : V)
		{
			if(adj[now].size()+adj2[now].size()+S[now].size()<adj[it].size()+adj2[it].size()+S[it].size()) swap(now, it);
			
			for(auto jt : adj2[it]) adj2[now].push_back(jt);
			for(auto jt : adj[it])
			{
				auto pt=S[now].lower_bound(jt.first);
				if(pt!=S[now].end() && *pt==jt.first) adj2[now].push_back(jt);
				else adj[now].insert(jt);
			}
			for(auto jt : S[it])
			{
				for(auto pt=adj[now].lower_bound({jt, 0}); pt!=adj[now].end() && pt->first==jt; pt=adj[now].erase(pt)) adj2[now].push_back(*pt);
				S[now].insert(jt);
			}
			uf2.Union(it, now);
			dead[it]=true;
		}

		while(!adj2[now].empty() && uf2.Find(adj2[now].back().second)==now) adj2[now].pop_back();

		if(!adj2[now].empty())
		{
			assert(S[now].count(adj2[now].back().first));
			par[now]=uf2.Find(adj2[now].back().second);
			if(uf.Find(now)==uf.Find(par[now])) Q.push(now);
			else uf.Union(now, par[now]);
		}
		else par[now]=0;
	}
	for(int i=1; i<=N; i++) cnt[uf2.Find(i)]++;

	int val=N;
	set<int> SS;
	for(int i=1; i<=N; i++) if(par[uf2.Find(i)]==0) val=min(val, cnt[uf2.Find(i)]);
	for(int i=1; i<=N; i++) if(par[uf2.Find(i)]==0 && cnt[uf2.Find(i)]==val) SS.insert(uf2.Find(i));
	for(int i=1; i<=N; i++) if(SS.count(uf2.Find(i))) ans[i]=1;
	
	return vector<int>(ans+1, ans+N+1);
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33