Submission #1065111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065111		ArthuroWich	Keys (IOI21_keys)	C++17	37 / 100	3048 ms	55232 KiB

keys

#include "keys.h"
#include<bits/stdc++.h>
using namespace std;
int p[300005], vis[300005], reach[300005], k[300005];
vector<pair<int, int>> adj[300005];
set<int> conc[300005];
void dfs(int i, int o) {
	if (vis[i]) {
		return;
	}
	p[o]++;
	vis[i] = 1;
	reach[k[i]] = 1;
	while(!conc[k[i]].empty()) {
		int j = *conc[k[i]].begin();
		conc[k[i]].erase(conc[k[i]].begin());
		if (!vis[j]) {
			dfs(j, o);
		}
	} 
	for (auto [j, c] : adj[i]) {
		if (reach[c]) {
			dfs(j, o);
		} else if (!vis[j]) {
			conc[c].insert(j);
		}
	}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size(), m = c.size();
	for (int i = 0; i < n; i++) {
		k[i] = r[i];
	}
	set<int> e;
	for (int i = 0; i < m; i++) {
		adj[u[i]].push_back({v[i], c[i]});
		adj[v[i]].push_back({u[i], c[i]});
		e.insert(c[i]);
	}
	for (int i = 0; i < n; i++) {
		dfs(i, i);
		for (int j = 0; j < n; j++) {
			vis[j] = 0;
		}
		for (int j : e) {
			reach[j] = 0;
			conc[j].clear();
		}
	}
	int mn = p[0];
	for (int i = 1; i < n; i++) {
		mn = min(mn, p[i]);
	}
	vector<int> ans(n, 0);
	for (int i = 0; i < n; i++) {
		if (p[i] == mn) {
			ans[i] = 1;
		}
	}
	return ans;
}

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