Submission #598747

#	Time	Username	Problem	Language	Result	Execution time	Memory
598747		sofapuden	Keys (IOI21_keys)	C++17	100 / 100	2076 ms	271376 KiB

keys

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#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] ? p[x] = get(p[x]) : x;
	}

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

};

struct info {
	unordered_map<int,vector<int>> blo;
	unordered_set<int> unl;
};

vector<info> inf;
vector<int> vis;

bool step(vector<int> &r, vector<vector<pair<int,int>>> &gr, DSU &d){
	bool ok = 0;
	int n = r.size();
	vis.clear();
	vis.resize(n,0);
	queue<pair<int,int>> Q;
	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){
					ok = 1;
					d.unite(x.second,x.first);
					continue;
				}
				if(vis[x.first])continue;
				vis[x.first] = 1;
				for(auto y : gr[x.first]){
					if(inf[x.second].unl.count(y.second))Q.push({y.first,x.second});
					else inf[x.second].blo[y.second].push_back(y.first);
				}
				inf[x.second].unl.insert(r[x.first]);
				for(auto y : inf[x.second].blo[r[x.first]])Q.push({y,x.second});
				inf[x.second].blo[r[x.first]].clear();
			}
		}
	}
	return ok;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
	int n = r.size();
	int m = u.size();
	inf.resize(n);
	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]});
	}
	while(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: 30 / 30
• Subtask 5: 33 / 33