Submission #497116

#	Time	Username	Problem	Language	Result	Execution time	Memory
497116		NachoLibre	Keys (IOI21_keys)	C++17	100 / 100	1254 ms	257496 KiB

keys

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define vint vector<int>
using namespace std;
#ifndef wambule
// #include ".h"
#else
#endif

const int N = 300005;

struct vert {
	vert() {
		next = -1;
		size = 1;
	}
	set<pair<int, int> > locked;
	set<int> keys;
	set<int> unlocked;
	set<int> vertices;
	int next, size;

	void add_key(int key) {
		if(keys.find(key) != keys.end()) return;
		for(;;) {
			auto it = locked.lower_bound({key, 0});
			if(it == locked.end() || (*it).first != key) break;
			unlocked.insert((*it).second);
			locked.erase(it);
		}
		keys.insert(key);
	}
	void add_edge(int x, int y) {
		if(keys.find(y) != keys.end()) {
			unlocked.insert(x);
		} else {
			locked.insert({y, x});
		}
	}
};

int n, m;
int up[N], up2[N];
vert vx[N];
queue<int> evolution;
vector<int> done;

int P(int x) {
	return (up[x] < 0 ? x : up[x] = P(up[x]));
}
int P2(int x) {
	return (up2[x] < 0 ? x : up2[x] = P2(up2[x]));
}
int Sz(int x) {
	return -up[P(x)];
}

void merge(int x, int y) {
	if(vx[x].size < vx[y].size) {
		swap(vx[x], vx[y]);
	}
	up2[P2(y)] = P2(x);
	vx[x].size += vx[y].size;
	for(auto key : vx[y].keys) {
		vx[x].add_key(key);
	}
	for(auto edge : vx[y].locked) {
		vx[x].add_edge(edge.second, edge.first);
	}
	for(auto vertex : vx[y].unlocked) {
		vx[x].unlocked.insert(vertex);
	}
	for(auto vertex : vx[y].vertices) {
		vx[x].vertices.insert(vertex);
	}
}

void activate(int x) {
	x = P2(x);
	while(vx[x].unlocked.size() && P2(*vx[x].unlocked.begin()) == x) {
		vx[x].unlocked.erase(vx[x].unlocked.begin());
	}
	if(!vx[x].unlocked.size()) {
		done.push_back(x);
		return;
	}
	int y = P2(*vx[x].unlocked.begin());
	if(P(x) != P(y)) {
		up[P(x)] = P(y);
		vx[x].next = y;
	} else {
		for(;;) {
			int z = P2(vx[y].next);
			merge(x, y);
			y = z;
			if(y == x) break;
		}
		evolution.push(x);
	}
}

vint find_reachable(vint _R, vint _U, vint _V, vint _C) {
	n = _R.size();
	m = _U.size();
	vint ans(n, 0);
	for(int i = 0; i < n; ++i) {
		up[i] = up2[i] = -1;
		vx[i].vertices.insert(i);
		vx[i].add_key(_R[i]);
	}
	for(int i = 0; i < m; ++i) {
		int x = _U[i];
		int y = _V[i];
		int z = _C[i];
		// cout << x << " " << y << " " << z << endl;
		vx[x].add_edge(y, z);
		vx[y].add_edge(x, z);
	}
	for(int i = 0; i < n; ++i) {
		evolution.push(i);
	}
	while(evolution.size()) {
		activate(evolution.front());
		evolution.pop();
	}
	int fp = 1e9;
	for(int x : done) {
		fp = min(fp, vx[x].size);
	}
	for(int x : done) {
		if(vx[x].size == fp) {
			for(int y : vx[x].vertices) {
				ans[y] = 1;
			}
		}
	}
	return ans;
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	// vint v = find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
	// for(int i = 0; i < sz(v); ++i) {
	// 	if(v[i]) cout << i << " ";
	// }
	// cout << endl;

	vint v = find_reachable({0, 1, 1, 2, 2, 1, 2},
					   {0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
	                   {1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
	                   {0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
	for(int i = 0; i < sz(v); ++i) {
		if(v[i]) cout << i << " ";
	}
	cout << endl;
	return 0;
}
#endif

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