Submission #598733

#	Time	Username	Problem	Language	Result	Execution time	Memory
598733		sofapuden	Keys (IOI21_keys)	C++17	37 / 100	3062 ms	141212 KiB

keys

#include<bits/stdc++.h>

using namespace std;

struct DSU {
	int n;
	vector<int> p;

	DSU(int _n) : n(_n) {
		p.resize(n);
		iota(p.begin(),p.end(),0);
	}

	int get(int x){
		return x ^ p[x] ? get(p[x]) : p[x] = x;
	}

	void unite(int a, int b){
		a = get(a), b = get(b);
		p[a] = b;
	}

};

vector<int> step(vector<int> &r, vector<vector<pair<int,int>>> &gr, DSU &d){
	int n = r.size();
	queue<pair<int,int>> Q;
	vector<int> vis(n,0);
	vector<unordered_map<int,vector<int>>> blo(n);
	vector<set<int>> unl(n);
	for(int i = 0; i < n; ++i){
		if(i == d.get(i))Q.push({i,i});
	}
	while(Q.size()){
		auto x = Q.front();
		Q.pop();
		if(x.second != d.get(x.second))continue;
		if(d.get(x.first) != x.second){
			d.unite(x.second,x.first);
			continue;
		}
		if(vis[x.first])continue;
		vis[x.first] = 1;
		for(auto y : gr[x.first]){
			if(unl[x.second].count(y.second))Q.push({y.first,x.second});
			else blo[x.second][y.second].push_back(y.first);
		}
		unl[x.second].insert(r[x.first]);
		for(auto y : blo[x.second][r[x.first]])Q.push({y,x.second});
		blo[x.second][r[x.first]].clear();
	}
	return vis;
}

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 d(n);
	vector<vector<pair<int,int>>> gr(n);
	for(int i = 0; i < m; ++i){
		gr[u[i]].push_back({v[i],c[i]});
		gr[v[i]].push_back({u[i],c[i]});
	}
	for(int i = 0; i < 20; ++i)step(r,gr,d);	
	vector<int> vis = step(r,gr,d);
	vector<int> nsiz(n,0);
	int mn = n+1;
	for(int i = 0; i < n; ++i){
		if(vis[i])nsiz[d.get(i)]++;
	}
	for(int i = 0; i < n; ++i){
		mn = min(mn,nsiz[d.get(i)]);
	}
	for(int i = 0; i < n; ++i){
		if(mn != nsiz[d.get(i)])vis[i] = 0;
	}
	return vis;
}

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