Submission #609588

#	Time	Username	Problem	Language	Result	Execution time	Memory
609588		Ozy	Keys (IOI21_keys)	C++17	37 / 100	184 ms	29444 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 2000
#define padre first
#define num second

vector<int> res;
lli n,m,a,act,ini;
pair<lli,lli> uf[MAX+2];

lli vis[MAX+2];
vector<pair<lli,lli> > aristas[MAX+2];
queue<lli> cola;
vector<int> llaves[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;

    if (b == ini) swap(a,b);

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

    if (llaves[a].size() < llaves[b].size()) swap(llaves[a], llaves[b]);
    for (auto bb : llaves[b]) llaves[a].push_back(bb);
}

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();
	res.resize(n,0);

	rep(i,0,m-1) aristas[c[i]].push_back({u[i],v[i]});

    rep(i,0,n-1) {
        ini = i;
        rep(j,0,n-1) {
            uf[j] = {j,1};
            llaves[j].clear();
            llaves[j].push_back(r[j]);
            vis[j] = 0;
        }

        cola.push(r[i]);
        while (!cola.empty()) {
            act = cola.front();
            cola.pop();
            if (vis[act] == 1) continue;
            vis[act] = 1;

            for (auto k : aristas[act]) une(k.first,k.second);

            for (auto ll : llaves[ini]) if (vis[ll] == 0) cola.push(ll);
            llaves[ini].clear();
        }

        res[i] = uf[i].num;
    }

	int peor = 1<<30;
	rep(i,0,n-1) 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: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33