Submission #617566

#	Time	Username	Problem	Language	Result	Execution time	Memory
617566		amunduzbaev	Keys (IOI21_keys)	C++17	37 / 100	165 ms	17820 KiB

keys

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

#ifndef EVAL
#include "grader.cpp"
#endif

const int N = 2005;
vector<int> edges[N], yet[N];
int a[N], E[N], used[N], C[N], vis[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++){
		a[i] = r[i];
	}
	
	for(int i=0;i<m;i++){
		E[i] = u[i] ^ v[i];
		edges[u[i]].push_back(i);
		edges[v[i]].push_back(i);
	}
	
	int res = n;
	vector<int> p;
	for(int i=0;i<n;i++){
		memset(used, 0, sizeof used);
		memset(C, 0, sizeof C);
		memset(vis, 0, sizeof vis);
		for(int i=0;i<n;i++) yet[i].clear();
		
		queue<int> q;
		q.push(i);
		vis[i] = 1;
		int cnt = 0;
		
		auto cler = [&](int c){
			C[c] = 1;
			for(auto j : yet[c]){
				if(!vis[u[j]]){
					vis[u[j]] = 1;
					q.push(u[j]);
				} if(!vis[v[j]]){
					vis[v[j]] = 1;
					q.push(v[j]);
				}
			}
		};
		
		while(!q.empty()){
			int u = q.front(); q.pop();
			cnt++;
			if(!C[a[u]]){
				cler(a[u]);
			}
			
			for(auto j : edges[u]){
				int x = E[j] ^ u;
				if(C[c[j]]){
					if(!vis[x]){
						vis[x] = 1;
						q.push(x);
					}
				} else {
					yet[c[j]].push_back(j);
				}
			}
		}
		
		if(cnt < res) p.clear(), res = cnt;
		if(res == cnt) p.push_back(i);
	}
	
	vector<int> ans(n);
	for(auto x : p) ans[x] = 1;
	
	return ans;
}

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