Submission #816907

#	Time	Username	Problem	Language	Result	Execution time	Memory
816907		vjudge1	Keys (IOI21_keys)	C++17	20 / 100	3046 ms	27516 KiB

keys

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <iomanip>
using namespace std;

const int nax = (int)2e5;
struct DSU{
	int p[nax], sz[nax];

	void init(int N){
		for (int i = 0; i < N; i++){
			p[i] = i;
			sz[i] = 1;
		}
	}

	int f(int a){
		if (p[a] == a)return a;
		return p[a] = f(p[a]);
	}

	bool merge(int a, int b){
		a = f(a), b = f(b);
		if (a == b)return false;
		if (sz[a] < sz[b])swap(a,b);
		sz[a] += sz[b];
		p[b] = a;
		return true;
	}
};

vector<pair<int,int>>adj[nax + 1];

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	std::vector<int> ans(r.size(), 1);
	int n = r.size();
	for (int i = 0; i < (int)u.size(); i++){
		adj[v[i]].push_back({u[i], c[i]});
		adj[u[i]].push_back({v[i],c[i]});
	}
	vector<int>keys(n + 1, 0);
	vector<int>visited(n + 1,0);
	int cnt = 0;
	function<void(int)>dfs = [&](int u){
		if (visited[u])return;
		cnt++;
		visited[u] = 1;
		keys[r[u]] = 1;
		for (auto next : adj[u]){
			if (keys[next.second] == 1){
				dfs(next.first);
			}
		}
	};
	vector<int>odg(n,0);
	int best = (int)1e9;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			keys[j] = 0;
		}
		keys[r[i]] = 1;
		for (int j = 0; j < 200; j++){
			for (int k = 0; k < n; k++){
				visited[k] = 0;
			}
			cnt = 0;
			dfs(i);
			best = min(best,cnt);
			odg[i] = cnt;
		}
	}
	for (int i = 0; i < n; i++){
		ans[i] = 0;
		if (odg[i] == best)ans[i] = 1;
	}
	return ans;
}

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