Submission #1059722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059722		pcc	Keys (IOI21_keys)	C++17	100 / 100	591 ms	126040 KiB

keys

#include <vector>
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 3e5+10;

set<int> heads;

struct DSU{
	set<int> keys[mxn];
	vector<pii> edges[mxn];
	int dsu[mxn],sz[mxn];
	DSU(){
		iota(dsu,dsu+mxn,0);
		fill(sz,sz+mxn,1);
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(heads.find(b) != heads.end())heads.erase(b);
		if(sz[a]<sz[b])swap(a,b);
		dsu[b] = a;
		sz[a] += sz[b];
		if(edges[a].size()<edges[b].size())edges[a].swap(edges[b]);
		if(keys[a].size()<keys[b].size())keys[a].swap(keys[b]);
		for(auto &i:keys[b])keys[a].insert(i);
		while(!edges[b].empty()){
			auto now = edges[b].back();edges[b].pop_back();
			if(root(now.fs) == a)continue;
			edges[a].push_back(now);
		}
		return;
	}
};

DSU dsu;
int N;

namespace SHRINK{
	vector<int> paths[mxn];
	bitset<mxn> done;
	int idx[mxn],low[mxn];
	vector<int> st;
	int cnt = 0;
	bool flag = false;
	void dfs(int now){
		idx[now] = low[now] = ++cnt;
		st.push_back(now);
		for(auto nxt:paths[now]){
			if(done[nxt])continue;
			if(!idx[nxt]){
				dfs(nxt);
				low[now] = min(low[now],low[nxt]);
			}
			else low[now] = min(low[now],idx[nxt]);
		}
		if(low[now] == idx[now]){
			if(st.back() != now)flag = true;
			while(st.back() != now){
				dsu.onion(now,st.back());
				done[st.back()] = true;
				st.pop_back();
			}
			done[st.back()] = true;
			st.pop_back();
		}
		return;
	}
	bool GO(){
		cnt = 0;
		flag = false;
		for(auto &now:heads){
			for(auto &[nxt,w]:dsu.edges[now]){
				nxt = dsu.root(nxt);
				if(nxt != now&&dsu.keys[now].find(w) != dsu.keys[now].end()){
					paths[now].push_back(nxt);
				}
			}
		}
		for(auto &i:heads){
			if(!done[i])dfs(i);
		}
		for(auto &i:heads){
			done[i] = false;
			idx[i] = low[i] = 0;
		}
		return flag;
	}
}

namespace ANSWER{
	bitset<mxn> leaf;
	vector<int> GO(){
		leaf.set();
		int mn = 1e9;
		for(auto &now:heads){
			for(auto &[nxt,w]:dsu.edges[now]){
				nxt = dsu.root(nxt);
				if(nxt == now)continue;
				if(dsu.keys[now].find(w) != dsu.keys[now].end())leaf[now] = false;
			}
			if(leaf[now])mn = min(mn,dsu.sz[now]);
		}
		vector<int> ans(N,0);
		for(int i = 0;i<N;i++){
			int now = dsu.root(i);
			if(!leaf[now]||dsu.sz[now] != mn)ans[i] = false;
			else ans[i] = true;
		}
		return ans;
	}
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	N = r.size();
	for(int i = 0;i<N;i++)heads.insert(i);
	for(int i = 0;i<N;i++){
		dsu.keys[i].insert(r[i]);
	}
	for(int i = 0;i<u.size();i++){
		int a = u[i],b = v[i],tp = c[i];
		dsu.edges[a].push_back(pii(b,tp));
		dsu.edges[b].push_back(pii(a,tp));
	}
	int cnt = 0;
	while(SHRINK::GO()){
		cnt++;
	}
	assert(cnt<=30);
	cerr<<cnt<<" epoches"<<endl;
	return ANSWER::GO();
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:129:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |  for(int i = 0;i<u.size();i++){
      |                ~^~~~~~~~~

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