Submission #1050452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050452		Zicrus	Keys (IOI21_keys)	C++17	37 / 100	3091 ms	28540 KiB

keys

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n;
vector<vector<pair<ll, ll>>> edges;
vector<int> r;

vector<ll> lnk;
vector<ll> sz;

ll find(ll a) {
    if (a != lnk[a]) lnk[a] = find(lnk[a]);
    return lnk[a];
}

bool unite(ll a, ll b) {
    a = find(a); b = find(b);
    if (a == b) return false;
    if (sz[a] > sz[b]) swap(a, b);
    lnk[a] = b;
    sz[b] += sz[a];
    return true;
}

ll solve(ll start) {
    lnk = vector<ll>(n);
    sz = vector<ll>(n, 1);
    for (int i = 0; i < n; i++) lnk[i] = i;
    vector<vector<ll>> adj(n);
    vector<bool> vst(n);
    vector<bool> hasKey(n);

    queue<ll> q;
    q.push(start);
    while (!q.empty()) {
        ll cur = q.front(); q.pop();
        if (vst[cur]) continue;
        vst[cur] = true;
        if (!hasKey[r[cur]]) {
            for (auto &e : edges[r[cur]]) {
                if (!unite(e.first, e.second)) continue;
                if (vst[e.first] || vst[e.second]) {
                    q.push(e.first);
                    q.push(e.second);
                }
                adj[e.first].push_back(e.second);
                adj[e.second].push_back(e.first);
            }
        }
        for (auto &e : adj[cur]) {
            q.push(e);
        }
    }

    return sz[find(start)];
}

vector<int> find_reachable(vector<int> r1, vector<int> u, vector<int> v, vector<int> c) {
    r = r1;
    n = r.size();
	edges = vector<vector<pair<ll, ll>>>(n);
    for (int i = 0; i < c.size(); i++) {
        edges[c[i]].push_back({u[i], v[i]});
    }

    vector<int> res(n);
    int mn = 1ll << 30ll;
    for (int i = 0; i < n; i++) {
        res[i] = solve(i);
        mn = min(mn, res[i]);
    }
    for (auto &e : res) {
        e = e == mn;
    }

    return res;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < c.size(); i++) {
      |                     ~~^~~~~~~~~~

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