Submission #609557

#	Time	Username	Problem	Language	Result	Execution time	Memory
609557		Ozy	Keys (IOI21_keys)	C++17	9 / 100	100 ms	14572 KiB

keys

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 300000
#define padre first
#define num second

lli n,m,a;
pair<lli,lli> uf[MAX+2];

lli sube(lli a) {
    if (uf[a].padre == a) return a;
    uf[a].padre = sube(uf[a].padre);
    return uf[a].padre;
}

void une(lli a ,lli b) {

    a = sube(a);
    b = sube(b);

    if (a==b) return;

    uf[b].padre = a;
    uf[a].num += uf[b].num;
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {

	n = r.size();
	m = u.size();

	rep(i,0,n-1) uf[i] = {i,1};

	rep(i,0,m-1) une(u[i],v[i]);

	int peor = 1<<30;
	vector<int> res;
	res.resize(n,0);
	rep(i,0,n-1) {
        if (r[i] != 0) res[i] = 1;
        else {
            a = sube(i);
            res[i] = uf[a].num;
        }

        peor = min(res[i],peor);
	}

	rep(i,0,n-1) if (res[i] == peor) res[i] = 1;
	else res[i] = 0;

	return res;
}

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