Submission #1107183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107183		pit4h	Keys (IOI21_keys)	C++17	39 / 100	484 ms	143796 KiB

keys

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

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i= (a); i < (b); i++)
#define per(i,a,b) for(int i = (b) - 1; i >= (a); i--)

#ifdef LOCAL
template<class A, class B> auto& operator<<(auto &o, pair<A, B> p) { return o << '(' << p.x << ", " << p.y << ')'; }
auto& operator<<(auto& o, auto a) {
	o << "{";
	for (auto b : a) o << b << ", ";
	return o << "}";
}
void dump(auto... x) { ((cerr << x << ", "), ...) << "\n"; }
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) ;
#endif

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const long int SEED = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(SEED);

const int MAXN = 3e5 + 5;

int n;
vi r;
map<int, vi> g[MAXN];
set<int> ready[MAXN], all_keys[MAXN];

void ins_edge(map<int,vi>& M, int c, int dst) {
	if (!M.count(c)) {
		M[c] = vi();
	}
	M[c].eb(dst);
}

bool check_empty(map<int,vi>& M, int c) {
	if (!M.count(c)) return true;
	return M[c].empty();
}

int vis[MAXN], reachable[MAXN];
int f[MAXN], cnt[MAXN];

int find(int x) {
	if (f[x] != x) f[x] = find(f[x]);
	return f[x];
}

bool unite(int x, int y) {
	x = find(x); y = find(y);
	assert(vis[x] == 1 && vis[y] == 1);
	if (x == y) return false;
	if (cnt[x] < cnt[y]) swap(x,y);

	f[y] = x;

	cnt[x] += cnt[y];
	cnt[y] = 0;

	for (int i: ready[y]) {
		ready[x].insert(i);
	}
	ready[y].clear();
	for (auto& [c, vec]: g[y]) {
		for (int i: vec) {
			ins_edge(g[x], c, i);
			if (all_keys[x].count(c)) {
				ready[x].insert(c);
			}
		}
	}
	g[y].clear();
	for (int i: all_keys[y]) {
		all_keys[x].insert(y);
		if (!check_empty(g[x], i)) {
			ready[x].insert(i);	
		}
	}
	all_keys[y].clear();

	return true;
}

void solve(int x) {
	debug("solve", x);
	vi vec = {x};
	vis[x] = 1;

	while (!vec.empty()) {
		int cur = vec.back();
		debug(cur, find(cur));
		cur = find(cur);

		debug(ready[cur]);
		if (ready[cur].empty()) {
			debug("ready empty");
			debug("final node representant candidate", cur, cnt[cur]); 
			reachable[cur] = cnt[cur];
			vis[cur] = 2;
			vec.pop_back();
			break;
		}

		int c = *ready[cur].begin();
		debug(c);

		vi &neigh = g[cur][c];
		debug(neigh);
		if (neigh.empty()) {
			debug("neigh empty");
			ready[cur].erase(c);
			continue;
		}

		int nxt = neigh.back();
		neigh.pop_back();
		debug(nxt, find(nxt));
		nxt = find(nxt);

		if (!vis[nxt]) {
			debug("append", nxt);
			vis[nxt] = 1;
			vec.eb(nxt);
		}
		else if (vis[nxt] == 2) {
			debug("current stack is not in final set", vec);	
			break;
		}
		else if (vis[nxt] == 1) {
			debug("unite+");
			while (find(vec.back()) != find(nxt)) {
				debug(vec.back(), nxt);
				unite(vec.back(), nxt);	
				vec.pop_back();
			}
			debug("unite-");
		}
		else {
			debug("vis kinda weird", nxt, vis[nxt]);
			assert(false);
		}
	}

	debug("while finished", vec);
	
	for (int i: vec) {
		vis[find(i)] = 2;
	}

}

void init() {
	rep(i,0,n) {
		f[i] = i;
		cnt[i] = 1;
	}
}

vi find_reachable(vi _r, vi u, vi v, vi c) {
	n = sz(_r);

	init();

	r = _r;
	rep(i,0,sz(u)) {
		ins_edge(g[u[i]], c[i], v[i]);	
		ins_edge(g[v[i]], c[i], u[i]);
	}

	rep(i,0,n) {
		ready[i].insert(r[i]);
		all_keys[i].insert(r[i]);
		reachable[i] = n + 1;
	}

	rep(i,0,n) {
		if (!vis[find(i)]) {
			solve(find(i));
		}
	}

	vi ans(n);

	int min_reachable = n;
	rep(i,0,n) {
		ckmin(min_reachable, reachable[i]);
	}

	rep(i,0,n) {
		ans[i] = (reachable[find(i)] == min_reachable?1:0);
	}
	return ans;
}

#ifdef LOCAL
int main() {
	int _n, _m; cin>>_n>>_m;
	vi _r(_n), _u(_m), _v(_m), _c(_m);
	rep(i,0,_n) {
		cin>>_r[i];
	}
	rep(i,0,_m) {
		cin>>_u[i];
	}
	rep(i,0,_m) {
		cin>>_v[i];
	}
	rep(i,0,_m) {
		cin>>_c[i];
	}

	vi ANSWER = find_reachable(_r, _u, _v, _c);
	debug(ANSWER);
}
#endif

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