Submission #1336929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1336929		liptonek	Keys (IOI21_keys)	C++20	0 / 100	3 ms	344 KiB

keys

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

const int MAX_N=300005;

struct DSU 
{
    vector<int> p;

	DSU(int n) : p(n) 
	{
        iota(p.begin(),p.end(),0);
    }
    
	int find(int i) 
	{
        int root=i;
    
		while(p[root]!=root) 
		{
			root=p[root];
		}

        while(p[i]!=root) 
		{
            int next=p[i];
        
			p[i]=root;
            i=next;
        }
        
		return root;
    }

    void unite(int i, int j) 
	{
        int root_i=find(i);
        int root_j=find(j);
    
		if(root_i!=root_j) 
		{
			p[root_i]=root_j;
		}
    }
};

vector<pair<int,int>> adj[MAX_N];

int status[MAX_N];
int vis[MAX_N];
int has[MAX_N];

vector<int> waiting[MAX_N];

int res[MAX_N];

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) 
{
    int n=r.size();
    int m=u.size();

    for(int i=0; i<n; i++) 
	{
        adj[i].clear();
    
		status[i]=0;
        vis[i]=-1;
        has[i]=-1;
        res[i]=n+1;
    
		waiting[i].clear();
    }

    for(int i=0; i<m; i++) 
	{
        adj[u[i]].push_back({v[i],c[i]});
        adj[v[i]].push_back({u[i],c[i]});
    }

    DSU dsu(n);
    
	int timer=0;

    for(int i=0; i<n; i++) 
	{
        if(status[dsu.find(i)]!=0) 
		{
			continue;
		}

        vector<int> path;
        
		int curr=dsu.find(i);

        while(true) 
		{
            status[curr]=1;
        
			path.push_back(curr);
            
            timer++;
        
			vector<int> q={curr};
        
			vis[curr]=timer;
            
            vector<int> skeys,swait;
        
			int head=0;
            int next=-1;

            while(head<(int)q.size()) 
			{
                int x=q[head++];
                int k=r[x];
                
                if(has[k]!=timer) 
				{
                    has[k]=timer;
                
					skeys.push_back(k);
                
					for(int w : waiting[k]) 
					{
                        if(vis[w]!=timer) 
						{
                            int root=dsu.find(w);
                        
							if(root!=curr) 
							{ 
								next=root; 
								
								goto found; 
							}

                            vis[w]=timer;
                            
							q.push_back(w);
                        }
                    }

                    waiting[k].clear();
                }

                for(auto& edge : adj[x]) 
				{
                    int y=edge.first;
					int req=edge.second;
                
					if(has[req]==timer) 
					{
                        if(vis[y]!=timer) 
						{
                            int root=dsu.find(y);
                        
							if(root!=curr) 
							{ 
								next=root;
								
								goto found; 
							}
                            
							vis[y]=timer;
                            
							q.push_back(y);
                        }
                    }
					else 
					{
                        if(vis[y]!=timer) 
						{
                            waiting[req].push_back(y);
                            swait.push_back(req);
                        }
                    }
                }
            }

            found:

            for(int sw : swait) 
			{
				waiting[sw].clear();
			}

            if(next==-1) 
			{
                res[curr]=q.size();
            
				for(int node : path) 
				{
					status[node]=2;
				}
            
				break;
            } 
			else 
			{
                next=dsu.find(next);
            
				if(status[next]==1) 
				{
                    while(path.back()!=next) 
					{
                        int top=path.back(); 
						path.pop_back();
                    
						dsu.unite(top,next);
                    }

                    curr=dsu.find(next);
                    
					status[curr]=0; 
                    
					path.pop_back(); 
                    
					break;
                } 
				else if(status[next]==2) 
				{
                    for(int node : path) 
					{
						status[node]=2;
					}

                    break;
                } 
				else 
				{
                    curr=next;
                }
            }
        }
    }

    int val=n+1;
    
	for(int i=0; i<n; i++) 
	{
        int root=dsu.find(i);
    
		if(status[root]==2) 
		{
			val=min(val,res[root]);
		}
    }

    vector<int> ans(n,0);
    
	for(int i=0; i<n; i++) 
	{
        if(res[dsu.find(i)]==val) 
		{
			ans[i]=1;
		}
    }
    
	return ans;
}

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