Submission #603177

#	Time	Username	Problem	Language	Result	Execution time	Memory
603177		FatihSolak	Keys (IOI21_keys)	C++17	67 / 100	604 ms	112304 KiB

keys

#include <bits/stdc++.h>
#define N 300005
using namespace std;
int group[N];
int find(int a){
	if(a == group[a])return a;
	return group[a] = find(group[a]);
}
bool merge(int a,int b){
	a = find(a);
	b = find(b);
	if(a == b)
		return 0;
	group[a] = b;
	return 1;
}
int low[N];
int tin[N];
bool is_bridge[2*N];
int vis[N];
bool vis2[N];
bool nowkeys[N];
vector<int> key[N];
vector<int> edges[N];
vector<pair<int,int>> adj[N];
vector<int> adj0[N];
int timer;
int tmp = -1;
void dfs(int v,int par){
	tin[v] = timer++;
	low[v] = tin[v];
	vis[v] = tmp;
	for(auto u:adj[v]){
		if(u.first == par){
			continue;
		}
		if(vis[u.second] != -1){
			is_bridge[u.first] = 1;
			if(vis[u.second] != vis[v]){
				is_bridge[u.first] = 1;
			}
			else low[v] = min(low[v],tin[u.second]);
			continue;
		}
		dfs(u.second,u.first);
		if(low[u.second] > tin[v]){
			is_bridge[u.first] = 1;
		}
		low[v] = min(low[v],low[u.second]);
	}
}
void dfs2(int v){
	vis2[v] = 1;
	for(auto u:adj[v]){
		if(is_bridge[u.first])continue;
		merge(v,u.second);
		if(vis2[u.second])continue;
		dfs2(u.second);
	}
}
int sz[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();
	vector<int> p(n,0);
	for(int i = 0;i<m;i++){
		adj0[u[i]].push_back(i);
		adj0[v[i]].push_back(i);
	}
	for(int i = 0;i<n;i++){
		group[i] = i;
	}
	for(int x = 0;x<3;x++){
		for(int i = 0;i<n;i++){
			key[i].clear();
			edges[i].clear();
			adj[i].clear();
			vis[i] = -1;
			vis2[i] = 0;
			sz[i] = 0;
			nowkeys[i] = 0;
		}
		for(int i = 0;i<2*m;i++){
			is_bridge[i] = 0;	
		}
		for(int i = 0;i<n;i++){
			key[find(i)].push_back(r[i]);
			for(auto x:adj0[i]){
				edges[find(i)].push_back(x);
			}
		}
		for(int i = 0;i<n;i++){
			if(i != find(i))continue;
			for(auto x:key[i]){
				nowkeys[x] = 1;
			}
			for(auto x:edges[i]){
				if(nowkeys[c[x]]){
					if(find(u[x]) != i)
						adj[i].push_back({x,find(u[x])});
					if(find(v[x]) != i)
						adj[i].push_back({x+m,find(v[x])});
				}
			}
			for(auto x:key[i]){
				nowkeys[x] = 0;
			}
		}
		timer = 0;
		for(int i = 0;i<n;i++){
			if(vis[i] == -1 && i == find(i)){
				tmp = i;
				dfs(i,-1);
			}
		}
		for(int i = 0;i<n;i++){
			if(i == find(i) && !vis2[i]){
				dfs2(i);
			}
		}
		for(int i = 0;i<n;i++){
			sz[find(i)]++;
		}
		int mini = 1e9;
		for(int i = 0;i<n;i++){
			if(sz[i] && adj[i].empty())
				mini = min(mini,sz[i]);
		}
		for(int i = 0;i<n;i++){
			if(sz[find(i)] == mini && adj[find(i)].empty()){
				p[i] = 1;
			}
			else p[i] = 0;
		}
	}

	return p;
}

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