Submission #1053519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053519		fuad27	Keys (IOI21_keys)	C++17	100 / 100	870 ms	284416 KiB

keys

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
vector<int> u, v, c;
struct node {
	unordered_set<int> cols;
	vector<int> goodEdges;
	unordered_set<int> curnodes;
	unordered_map<int,vector<int>> badEdges;
	int cntEdges=0;
	int getGoodEdge() {
		while(goodEdges.size()) {
				if(curnodes.find(u[goodEdges.back()])==curnodes.end())break;
				if(curnodes.find(v[goodEdges.back()])==curnodes.end())break;
				goodEdges.pop_back();
		}
		if(goodEdges.size())return goodEdges.back();
		return -1;
	}
	bool isHere(int vv) {
		if(curnodes.find(vv)!=curnodes.end())return true;
		return false;
	}
};
struct dsu {
	vector<int> e;
	int cc=0;
	dsu(int n) {
		e=vector<int>(n, -1);
		cc=n;
	}
	int get(int x) {
		if(e[x]<0)return x;
		return e[x]=get(e[x]);
	}
	bool unite(int x, int y) {
		x=get(x),y=get(y);
		if(x==y)return false;
		if(-e[x] < -e[y]){
			swap(x, y);
		}
		cc--;
		e[x]+=e[y];
		e[y] = x;
		return true;
	}
};
const int N=300000;
node nd[N];
vector<int> find_reachable(vector<int> r, vector<int> U, vector<int> V, vector<int> C) {
	int n = r.size(), m = U.size();
	vector<int> pending(n);
	iota(pending.begin(), pending.end(), 0);
	vector<int> id(n), par(n, -1);
	iota(id.begin(), id.end(), 0);
	u=U;
	v=V;
	c=C;
	for(int i = 0;i<n;i++) {
		id[i] = i;
		nd[i].cols.insert(r[i]);
		nd[i].curnodes.insert(i);
		nd[i].cntEdges++;
	}
	for(int i = 0;i<m;i++) {
		if(r[u[i]] == c[i]) {
			nd[u[i]].goodEdges.push_back(i);
		}
		else nd[u[i]].badEdges[c[i]].push_back(i);
		if(r[v[i]] == c[i]) {
			nd[v[i]].goodEdges.push_back(i);
		}
		else nd[v[i]].badEdges[c[i]].push_back(i);
		nd[u[i]].cntEdges++;
		nd[v[i]].cntEdges++;
	}
	dsu d(n);
	vector<int> res(n, 1e9);
	while(pending.size()) {
		int at = id[pending.back()];
		pending.pop_back();
		int E = nd[at].getGoodEdge();
		if(E == -1) {
			for(int j:nd[at].curnodes)res[j]=nd[at].curnodes.size();
			continue;
		}
		int to =0;
		if(nd[at].isHere(v[E]))to = u[E];
		else to = v[E];
		par[at] = to;
		if(!d.unite(id[par[at]], at)) {
			int cur = id[par[at]];
			while(cur!=at) {
				if(nd[cur].cntEdges > nd[at].cntEdges) {
					for(int j:nd[at].curnodes){
						nd[cur].curnodes.insert(j);
						id[j] = cur;
					}
					for(int j:nd[at].goodEdges)nd[cur].goodEdges.push_back(j);
					for(auto &j:nd[at].badEdges) {
						bool becomesGood=false;
						if(nd[cur].cols.find(j.first)!=nd[cur].cols.end())becomesGood=true;
						for(int k:j.second) {
							if(becomesGood)nd[cur].goodEdges.push_back(k);
							else nd[cur].badEdges[j.first].push_back(k);
						}
					}
					for(auto j:nd[at].cols) {
						if(nd[cur].badEdges.find(j)!=nd[cur].badEdges.end()) {
							for(int k:nd[cur].badEdges[j])nd[cur].goodEdges.push_back(k);
							nd[cur].badEdges[j].clear();
						}
						nd[cur].cols.insert(j);
					}
					nd[cur].cntEdges+=nd[at].cntEdges;
					at=cur;
				}
				else {
					swap(at, cur);
					for(int j:nd[at].curnodes){
						nd[cur].curnodes.insert(j);
						id[j] = cur;
					}
					for(int j:nd[at].goodEdges)nd[cur].goodEdges.push_back(j);
					for(auto &j:nd[at].badEdges) {
						bool becomesGood=false;
						if(nd[cur].cols.find(j.first)!=nd[cur].cols.end())becomesGood=true;
						for(int k:j.second) {
							if(becomesGood)nd[cur].goodEdges.push_back(k);
							else nd[cur].badEdges[j.first].push_back(k);
						}
					}
					for(auto j:nd[at].cols) {
						if(nd[cur].badEdges.find(j)!=nd[cur].badEdges.end()) {
							for(int k:nd[cur].badEdges[j])nd[cur].goodEdges.push_back(k);
							nd[cur].badEdges[j].clear();
						}
						nd[cur].cols.insert(j);
					}
					nd[cur].cntEdges+=nd[at].cntEdges;
					swap(at, cur);

				}
				cur = id[par[cur]];
			}
			par[at] = -1;
			pending.push_back(to);
		} else continue;
	}
	vector<int> ans(n);
	int mn = (*min_element(res.begin(), res.end()));
	for(int i = 0;i<n;i++) {
		if(res[i] == mn)ans[i] = 1;
	}
	return ans;
}

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