Submission #821768

#	Time	Username	Problem	Language	Result	Execution time	Memory
821768		alvingogo	Keys (IOI21_keys)	C++17	100 / 100	664 ms	55232 KiB

keys

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct DSU{
	vector<int> bo;
	void init(int n){
		bo.resize(n);
		iota(bo.begin(),bo.end(),0);
	}
	int find(int x){
		return bo[x]==x?x:bo[x]=find(bo[x]);
	}
	void merge(int x,int y){
		bo[find(x)]=find(y);
	}
}dsu;
vector<int> r;
vector<int> z,vis,ans,nxt,ret,dead;
vector<int> lst;
int sz=1e9;
vector<vector<int> > to;
vector<vector<pair<int,int> > > e;
void bfs(int x,int s){
	lst[x]=s;
	queue<int> q;
	q.push(x);
	while(q.size()){
		auto h=q.front();
		q.pop();
		if(dsu.find(h)!=x){
			dsu.merge(x,h);
			lst[dsu.find(h)]=s;
			for(auto y:nxt){
				to[y].clear();
			}
			nxt.clear();
			for(auto h:ans){
				z[r[h]]=0;
			}
			ans.clear();
			return;
		}
		if(vis[h]){
			continue;
		}
		vis[h]=1;
		ans.push_back(h);
		z[r[h]]=1;
		for(auto y:to[r[h]]){
			q.push(y);
		}
		to[r[h]].clear();
		for(auto y:e[h]){
			if(z[y.fs]){
				q.push(y.sc);
			}
			else{
				to[y.fs].push_back(y.sc);
				nxt.push_back(y.fs);
			}
		}
	}
	dead[x]=1;
	if(ans.size()<sz){
		ret=ans;
		sz=ans.size();
	}
	else if(ans.size()==sz){
		ret.insert(ret.end(),ans.begin(),ans.end());
	}
	for(auto y:nxt){
		to[y].clear();
	}
	nxt.clear();
	for(auto h:ans){
		z[r[h]]=0;
	}
	ans.clear();
}
vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> c) {
	int n=R.size();
	int m=u.size();
	dsu.init(n);
	e.resize(n);
	vis.resize(n);
	nxt.resize(n);
	lst.resize(n);
	z.resize(n);
	to.resize(n);
	dead.resize(n);
	r=R;
	for(int i=0;i<m;i++){
		e[u[i]].push_back({c[i],v[i]});
		e[v[i]].push_back({c[i],u[i]});
	}
	for(int j=1;;j++){
		int flag=0;
		fill(vis.begin(),vis.end(),0);
		for(int i=0;i<n;i++){
			if(!dead[i] && dsu.find(i)==i && lst[i]!=j){
				bfs(i,j);
				flag=1;
			}
		}
		if(flag==0){
			break;
		}
	}
	vector<int> rr(n);
	for(auto h:ret){
		rr[h]=1;
	}
	return rr;
}

Compilation message (stderr)

keys.cpp: In function 'void bfs(int, int)':
keys.cpp:68:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |  if(ans.size()<sz){
      |     ~~~~~~~~~~^~~
keys.cpp:72:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |  else if(ans.size()==sz){
      |          ~~~~~~~~~~^~~~

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