Submission #437006

#	Time	Username	Problem	Language	Result	Execution time	Memory
437006		wasa855	Keys (IOI21_keys)	C++17	100 / 100	2195 ms	155372 KiB

keys

#include "keys.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
mt19937 rnd(20041015);
#define fir first
#define sec second
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
namespace wasa855
{
	#define N 300005
	int fa[N],n;
	set<int> keys[N],G[N];
	set<pii> H[N];
	void att(int u,int v,int col)
	{
		if(u==v) return ;
		if(keys[u].find(col)!=keys[u].end()) G[u].insert(v);
		else H[u].emplace(col,v);
	}
	int find(int u) {return fa[u]==u?u:fa[u]=find(fa[u]);}
	void merge(int u,int v)
	{
		u=find(u),v=find(v);
		if(u==v) return ;
//		printf("merge %d %d\n",u,v);
		fa[v]=u;
//		if(keys[u].size()<keys[v].size()) swap(keys[u],keys[v]);
//		if(G[u].size()<G[v].size()) swap(G[u],G[v]);
//		if(H[u].size()<H[v].size()) swap(H[u],H[v]);
		if(keys[u].size()+G[u].size()+H[u].size()<keys[v].size()+G[v].size()+H[v].size()) swap(keys[u],keys[v]),swap(G[u],G[v]),swap(H[u],H[v]);
		for(int i:G[v]) G[u].insert(i);
		for(int i:keys[v])
		{
			auto pos=H[u].lower_bound({i,0});
			while(pos!=H[u].end()&&pos->fir==i)
			{
				G[u].insert(pos->sec);
				auto nxt=pos; pos++;
				H[u].erase(nxt);
			}
			keys[u].insert(i);
		}
		for(auto [c,v]:H[v]) att(u,find(v),c);
//		printf("out\n");
	}
	int vis[N],st[N],tp;
	void popfront(int u)
	{
//		printf("^ in %d\n",u);
		while(!G[u].empty())
		{
			int val=*G[u].begin();
			if(val!=find(val)&&find(val)!=u) G[u].insert(find(val)),G[u].erase(val);
			else if(find(val)==u) G[u].erase(val);
			else break;
		}
//		printf("out\n");
	}
	void work(int u)
	{
		st[++tp]=u,vis[u]=1;
		while(tp)
		{
			popfront(u);
			if(G[u].empty())
			{
				vis[st[tp--]]=2;
				u=st[tp];
				continue;
			}
			int v=*G[u].begin();
			G[u].erase(v);
//			printf("^ %d %d\n",u,v);
			if(vis[v]==2) continue;
			if(vis[v]==1)
			{
				while(st[tp]!=v) merge(v,st[tp]),vis[st[tp--]]=0;
				u=find(st[tp]);
			}
			if(vis[v]==0)
			{
				st[++tp]=v,vis[v]=1;
				u=v;
			}
		}
	}
	vector<int> Main(vector<int> a,vector<int> u,vector<int> v,vector<int> c)
	{
		n=a.size();
		for(int i=0;i<n;i++) fa[i]=i,keys[i].insert(a[i]);
		for(int i=0;i<(int)u.size();i++) att(u[i],v[i],c[i]),att(v[i],u[i],c[i]);
		for(int i=0;i<n;i++) if(!vis[i]) work(i);
//		for(int i=0;i<n;i++) printf("%d%c",find(i)," \n"[i==n-1]);
		vector<int> siz(n),dgr(n);
		for(int i=0;i<n;i++) siz[find(i)]++;
		for(int i=0;i<(int)u.size();i++)
		{
			u[i]=find(u[i]),v[i]=find(v[i]);
			if(u[i]==v[i]) continue;
			if(keys[u[i]].find(c[i])!=keys[u[i]].end()) dgr[u[i]]++;
			if(keys[v[i]].find(c[i])!=keys[v[i]].end()) dgr[v[i]]++;
		}
//		print(dgr);
		int mn=inf;
		for(int i=0;i<n;i++) if(find(i)==i&&!dgr[i]) mn=min(mn,siz[i]);
		vector<int> ans(n);
		for(int i=0;i<n;i++)
		{
			int u=find(i);
			if(!dgr[u]&&siz[u]==mn) ans[i]=1;
		}
		return ans;
	}
};
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
	return wasa855::Main(r,u,v,c);
}

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