Submission #436779

#	Time	Username	Problem	Language	Result	Execution time	Memory
436779		David_M	Keys (IOI21_keys)	C++17	37 / 100	2582 ms	24196 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define F first
#define S second
const int N=300005;

vi find_reachable(vi r, vi u, vi v, vi c){
	int n=r.size(), m=u.size();
	vi Ans(n, 0);
    pii ans[n];
    vector<pii> V[n];


	for(int j=0; j<m; j++){
	    int x=u[j], y=v[j], C=c[j];
		V[x].pb({y,C});
		V[y].pb({x,C});
	}

	for (int i=0; i<n; i++){ans[i].S=i;
        bool C[n], f[n];
        for (int j=0; j<n; j++)f[j]=C[j]=false;
        vi vv[n];
        C[r[i]]=true;
        queue<int> q;
        q.push(i);
        f[i]=true;
        while(!q.empty()){ans[i].F++;
            int x=q.front();
            q.pop();
            for (auto [y,c]:V[x]){
                if(!f[y]){
                    if(!C[c])vv[c].pb(y);
                    else f[y]=true,q.push(y);
                }
            }
            if(!C[r[x]]){for (auto k:vv[r[x]])if(!f[k])q.push(k),f[k]=true; C[r[x]]=true;}
        }
	}
	sort(ans, ans+n);
	int R=ans[0].F, o=0;
	while(ans[o].F==R){
        Ans[ans[o].S]=1;
        o++;
	}
	return Ans;
}

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