Submission #1041062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041062		ReLice	Keys (IOI21_keys)	C++17	100 / 100	589 ms	83648 KiB

keys

#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define vll vector<ll>
#define fr first
#define sc second
#define ins insert
#define sz size()
using namespace std;
const int N = 3e5 + 7;
const int inf = 1e9;
vector<vector<pair<ll,ll>>> g(N);
int p[N];
vll have(N,0);
vll vis(N,0);
ll cen[N];
vector<ll> r;
vector<vll> need(N);
vector<vll> cmp(N);
vll er,er2;
int n;
bool merge(ll a,ll b){
	a=p[a],b=p[b];
	cen[a]=cen[b];
	if(a==b)return false;
	if(cmp[a].sz>cmp[b].sz)swap(a,b);
	for(auto i : cmp[a]){
		cmp[b].pb(i);
		p[i]=b;
	}
	return true;
}
ll bfs(ll v){
	queue<ll> q;
	q.push(v);
	while(q.sz){
		ll x=q.front();
		q.pop();
		if(vis[x])continue;
		if(!have[r[x]]){
			for(auto i : need[r[x]]){
				if(p[x]!=p[i])return p[i];
				q.push(i);
			}
		}
		vis[x]=have[r[x]]=1;
		er.pb(x);
		for(auto i : g[x]){
			ll to=i.fr,key=i.sc;
			if(have[key]==0){
				need[key].pb(to);
				er2.pb(key);
			}else{
				if(p[to]!=p[x])return p[to];
				q.push(to);
			}
		}
	}
	return -1;
}
void cl(){
	for(auto i : er){
		have[r[i]]=vis[i]=0;
	}
	for(auto i : er2) need[i].clear();
	er.clear();
	er2.clear();
}

vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> c) {
	
	r=R;
	n = r.size();
	
	int m=u.size();
	
	for(int i=0;i<m;i++){
		g[u[i]].pb({v[i],c[i]});
		g[v[i]].pb({u[i],c[i]});
	}
	
	vector<int> ans(n,0);
	int mn=inf;
	set<int> st;
	for(int i=0;i<n;i++){
		cmp[i].pb(i);
		p[i]=i;
		cen[i]=i;
	}
	
	while(true){
		vll to(n,0);
		bool f=0;
		
		for(int i=0;i<n;i++){
			if(p[i]!=i) continue;
			
			to[i]=bfs(cen[i]);
			if(to[i]>=0)f=1;
			
			cl();
		}
		
		
		if(!f)break;
		for(int i=0;i<n;i++){
			if(p[i]!=i || to[i]==-1) continue;
			
			ll v=p[to[i]];
			
			if(p[i]==v)continue;
			
			merge(i,v);
		}
	}
	for(int i=0;i<n;i++){
		if(i!=p[i])continue;
		if(p[i]==i)bfs(cen[i]);
		
		for(auto j : er)ans[j]=er.sz;
		
		if(p[i]==i){
			mn=min(mn,ans[cen[i]]);
		}
		cl();
	}
	
	for(int i=0;i<n;i++){
		if(ans[i]==mn)ans[i]=1;
		else ans[i]=0;
	}
	return ans;
}

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