Submission #441355

#	Time	Username	Problem	Language	Result	Execution time	Memory
441355		fcmalkcin	Keys (IOI21_keys)	C++17	100 / 100	1809 ms	168988 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];
	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])
        {
            if(keys[u].count(c)) G[u].insert(v);
		    else H[u].emplace(c,v);
        }
//		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)
	{
	    stack<ll> st;
		st.push(u);
		vis[u]=1;
		while(!st.empty())
		{
		    auto u=st.top();
			popfront(u);
			if(G[u].empty())
			{
				vis[u]=2;
                st.pop();
				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.top()!=v) merge(v,st.top()),vis[st.top()]=0,st.pop();
			}
			else if(vis[v]==0)
			{
			    st.push(v);
			    vis[v]=1;
			}
		}
	}
	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++)
        {
             if(keys[u[i]].count(c[i])) G[u[i]].insert(v[i]);
		    else H[u[i]].emplace(c[i],v[i]);
           if(keys[v[i]].count(c[i])) G[v[i]].insert(u[i]);
		    else H[v[i]].emplace(c[i],u[i]);
        }
		for(int i=0;i<n;i++) if(!vis[i]&&find(i)==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);
}
/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.ans", "w", stdout);
    }
    ll n, m;
    cin>> n>> m;
    vector<int> r;
    for (int i=1; i<=n; i++)
    {
        int x;
        cin>> x;
        r.pb(x);
    }
    vector<int> u,v,c;
    for (int i=1; i<=m; i++)
    {
        int x, y, w;
        cin>> x>> y>> w;
        u.pb(x);
        v.pb(y);
        c.pb(w);
    }

    vector<int> ans=find_reachable(r,u,v,c);
    for (auto to:ans) cout <<to<<" ";

}*/

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