Submission #1053284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053284		MercubytheFirst	Keys (IOI21_keys)	C++17	0 / 100	0 ms	348 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 

vector<vector<pii> > g;
vector<vector<int> > dg, revdg;
vector<bool> vis;
vector<int> order;
vector<int> root, comp_sz;
int cur_comp;
void order_dfs(int v) {
	if(vis[v]) {
		return;
	}
	vis[v] = true;
	for(int to : dg[v]) {
		if(!vis[to]) 
			order_dfs(to);
	}
	order.push_back(v);
}


void comp_dfs(int v) {
	if(vis[v]) {
		return;
	}
	vis[v] = true;
	root[v] = cur_comp;
	comp_sz[cur_comp] += 1;
	for(int to : revdg[v]) {
		if(!vis[to]) {
			comp_dfs(to);
		}
	}
}

vector<signed> find_reachable(vector<signed> r, vector<signed> u, vector<signed> v, vector<signed> c) {
	int n = r.size();
	int m = u.size();
	g.assign(n, vector<pii>());
	dg.assign(n, vector<int>());
	revdg.assign(n, vector<int>());
	for(int i = 0; i < m; ++i) {
		g[u[i]].push_back({v[i], c[i]});
		g[v[i]].push_back({u[i], c[i]});
	}
	for(int i = 0; i < n; ++i) {
		for(auto [to, key] : g[i]) {
			if(key == r[i]) {
				dg[i].push_back(to);
				revdg[to].push_back(i);
			}
		}
	}
	vis.assign(n, false);
	for(int i = 0; i < n; ++i) {
		if(!vis[i]) {
			order_dfs(i);
		}
	}
	reverse(order.begin(), order.end());
	vis.assign(n, false);
	root.assign(n, -1);
	for(int x : order) {
		// cout << x << ' ';
		if(!vis[x]) {
			// cout << x << ' ';
			comp_sz.push_back(0);
			comp_dfs(x);
			cur_comp++;
		}
	}
	vector<int> outdeg(n);
	for(int i = 0; i < n; ++i) {
		assert(root[i] != -1);
		for(int to : dg[i]) {
			assert(root[to] != -1);
			if(root[to] != root[i]) {
				outdeg[root[i]]++;
			}
		}
	}
	vector<int> ans(n);
	for(int i = 0; i < n; ++i) {
		if(outdeg[root[i]] == 0) {
			ans[i] = 1;
		}
	}
	return ans;
}
/*
7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1
 
4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
1 3 2
*/

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