Submission #1048115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048115		vjudge1	Keys (IOI21_keys)	C++17	37 / 100	3041 ms	48572 KiB

keys

#include<bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
vector<pair<int,int>>adj[300100];
int col[300100],got[300100],went[300100],bst;
vector<int> onez;
bitset<300100>don;
VI unlocked[300100];
mt19937 rng(random_device{}());
int CDC;
void simul(int n){
	set<int>hav;
	CDC++;
	queue<int>q;
	q.push(n);
	int CNT=0;
	went[n]=CDC;
	while(q.size()){
		int x=q.front();
		q.pop();
		CNT++;
		if(CNT>bst)break;
		if(don[x]){CNT=1e9;break;}
		went[x]=CDC;
		if(got[col[x]]^CDC){
			got[col[x]]=CDC;
			for(auto i:unlocked[col[x]])
				if(went[i]^CDC)
					q.push(i),went[i]=CDC;
			unlocked[col[x]].clear();
			hav.erase(col[x]);
		}
		for(auto[v,c]:adj[x])
			if(got[c]==CDC) {
				if(went[v]^CDC)
					q.push(v),went[v]=CDC;
			}else unlocked[c].push_back(v),
				hav.insert(c);
	}
	don[n]=1;
	for(auto i:hav)
		unlocked[i].clear();
	if(CNT<bst)
		bst=CNT,onez.clear();
	if(CNT==bst)
		onez.push_back(n);
}
VI find_reachable(VI r, VI u, VI v, VI c) {
	bst=1e9;
	int n=r.size(),m=c.size();
	VI ord(n),ans(n);
	iota(ord.begin(),ord.end(),0);
	shuffle(ord.begin(),ord.end(),rng);
	for(int i=0;i<n;i++)
		col[i]=r[i];
	for(int i=0;i<m;i++)
		adj[u[i]].push_back({v[i],c[i]}),
		adj[v[i]].push_back({u[i],c[i]});
	for(auto i:ord)
		simul(i);
	don.reset();
	int x=onez.size();
	for(int i=0;i<x;i++)
		simul(onez[i]);
	for(int i=0;i<n;i++)
		if(went[i]>n)
			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