Submission #609756

#	Time	Username	Problem	Language	Result	Execution time	Memory
609756		StrawHatWess	Keys (IOI21_keys)	C++17	0 / 100	3083 ms	613100 KiB

keys

#include "keys.h"

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

#define FOR(i,a,b) for(int i=a; i<b; i++)

typedef vector<int>vi;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)


typedef pair<int,int>pi; 
#define fi first
#define se second
typedef vector<pi>vpi;
#define eb emplace_back

bool ckmin(int &x, int y){
	int f=x>y; 
	x=min(x,y); 
	return f; 
}

//-------


const int MX=3e5+10; 

int N,M; 
vpi adj[MX]; 

vi find_reachable(vi a, vi U, vi V, vi C){
	N=sz(a); M=sz(U); 

	FOR(i,0,M){
		int u=U[i], v=V[i];
		adj[u].eb(v,C[i]); 
		adj[v].eb(u,C[i]); 
	}

	vi ans; 
	int mn=2e9; 	
	FOR(s,0,N){
		vi vis(N,0); 
		vi vist(N,0); 
		queue<int>q; q.push(s); 

		int n=0; 
		while(sz(q)){
			int u=q.front(); q.pop(); 

			vis[u]=1; 
			vist[a[u]]=1; 
			n++; if(n>=mn) break; 

			FOR(u,0,N) if(vis[u]) for(auto it: adj[u]){
				int v=it.fi, t=it.se; 
				if(vist[t] && !vis[v]){
					q.push(v); 
				}
			}
		}

		vi vec; 
		FOR(i,0,N) if(vis[i]) vec.pb(i); 

		if(ckmin(mn,sz(vec))) ans={s}; 
		else if(mn==sz(vec)) ans.pb(s); 
	}



	vi res(N,0); 
	for(int x: ans) res[x]=1; 
	return res; 

}

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