Submission #609761

#	Time	Username	Problem	Language	Result	Execution time	Memory
609761		StrawHatWess	Keys (IOI21_keys)	C++17	37 / 100	3009 ms	29644 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), vist(N,0), vec; 
		vis[s]=1; vist[a[s]]=1; 

		queue<int>q; q.push(s); 
		
		vi wait[N]; 
		while(sz(q)){
			int u=q.front(); q.pop(); 
			
			vec.pb(u);

			for(auto it: adj[u]){
				int v=it.fi, t=it.se; 
				if(!vis[v]){
					if(vist[t]){
						q.push(v); 
						vis[v]=1; 
						vist[a[v]]=1; 	
					}
					else wait[t].pb(v); 
				}
			}

			for(int v: wait[a[u]]) if(!vis[v]){
				q.push(v); 
				vis[v]=1; 
				vist[a[v]]=1; 	
			}
			wait[a[u]].clear(); 
		}

		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: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33