Submission #816762

#	Time	Username	Problem	Language	Result	Execution time	Memory
816762		vjudge1	Keys (IOI21_keys)	C++17	0 / 100	1 ms	1748 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;
	}
};

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();
	DSU d;
	d.init(n);
	for (int i = 0; i < (int)u.size(); i++){
		if (c[i] == 0)d.merge(u[i], v[i]);
	}
	int best = 0;
	vector<int>odg(n);
	for (int i = 0; i < n; i++){
		odg[i] = 1;
		if (r[i] == 0)odg[i] = d.sz[d.f(i)];
		best = max(best, odg[i]);
	}

	for (int i = 0; i < n; i++){
		ans[i] = 0;
		if (odg[i] == best)ans[i] = 1;
	}
	return ans;
}

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