Submission #1050094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050094		vjudge1	Keys (IOI21_keys)	C++17	100 / 100	521 ms	61816 KiB

keys

#include<bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
struct dsu{
	int par[300100];
	int abp(int n){
		return par[n]?par[n]=abp(par[n]):n;
	}
	void merge(int a,int b){
		par[abp(a+1)]=abp(b+1);
	}
	int comp(int x){
		return abp(x+1)-1;
	}
} kirby;
vector<pair<int,int>>adj[300100];
int col[300100],got[300100],bst;
VI unlocked[300100],onez;
mt19937 rng(random_device{}());
int CDC;
bitset<300100>vis,dIe;
void simul(int n){
	queue<int>q;
	q.push(n);
	int hmm=1;
	CDC++;
	VI todo;
	set<int>res;
	while(q.size()){
		int x=q.front();
		res.insert(x);
		q.pop();
		if(kirby.comp(x)!=n){
			kirby.merge(n,x);
			vis[kirby.comp(x)]=1;
			hmm=0;
			break;
		}
		if(vis[x])
			continue;
		vis[x]=1;
		if(got[col[x]]^CDC){
			got[col[x]]=CDC;
			for(auto i:unlocked[col[x]])
				q.push(i);
		}
		for(auto[v,c]:adj[x])
			if(got[c]==CDC)
				q.push(v);
			else {
				if(unlocked[c].empty())
					todo.push_back(c);
				unlocked[c].push_back(v);
			}
	}
	for(auto i:todo)
		unlocked[i].clear();
	if(hmm) {
		if(res.size()<bst)
			bst=res.size(),onez.clear();
		if(res.size()==bst)
			for(auto i:res)
				onez.push_back(i);
		dIe[n]=1;
	}
}
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]});
	while(1){
		CDC++;
		int donn=0;
		for(int i=0;i<n;i++)
			if(!vis[i]&&kirby.comp(i)==i&&!dIe[i])
				donn=1,simul(i);
		vis.reset();
		if(!donn)break;
	}
	for(auto i:onez)
		ans[i]=1;
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'void simul(int)':
keys.cpp:59:16: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |   if(res.size()<bst)
      |      ~~~~~~~~~~^~~~
keys.cpp:61:16: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |   if(res.size()==bst)
      |      ~~~~~~~~~~^~~~~

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