Submission #435520

#	Time	Username	Problem	Language	Result	Execution time	Memory
435520		b00n0rp	Keys (IOI21_keys)	C++17	37 / 100	2597 ms	46780 KiB

keys

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define vi vector<int>
#define pb push_back
#define SZ(v) (int)v.size()
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define F first
#define S second
#define vpii vector<pii>

const int MX = 300005;

int n,m;

vpii adj[MX];
int cnt[MX];

int a[MX];
bool visvert[MX],viscol[MX];
vi gg[MX];

int cur;

void dfs(int u){
	visvert[u] = 1;
	cur++;
	for(auto v:adj[u]){
		if(visvert[v.F]) continue;
		if(viscol[v.S]) dfs(v.F);
		else gg[v.S].pb(v.F);
	}
	if(!viscol[a[u]]){
		viscol[a[u]] = 1;
		for(auto x:gg[a[u]]){
			if(!visvert[x]) dfs(x);
		}
	}
}

vector<signed> find_reachable(vector<signed> r, vector<signed> u, vector<signed> v, vector<signed> c) {
	n = SZ(r);
	m = SZ(u);
	REP(i,n) a[i] = r[i];
	REP(i,m){
		adj[u[i]].pb({v[i],c[i]});
		adj[v[i]].pb({u[i],c[i]});
	}
	REP(i,n){
		REP(j,n){
			visvert[j] = 0;
			viscol[j] = 0;
			gg[j].clear();
		}
		cur = 0;
		dfs(i);
		cnt[i] = cur;
	}
	vector<signed> ans(n,0);
	int mn = n;
	REP(i,n) remin(mn,cnt[i]);
	REP(i,n){
		if(cnt[i] == mn) ans[i] = 1;
	}
	return ans;
}

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