Submission #1061404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061404		Ignut	Keys (IOI21_keys)	C++17	37 / 100	3034 ms	37464 KiB

keys

/* Ignut
started: 16.08.2024
now: 16.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3e5 + 123;
int n;

vector<int> r;
vector<pair<int, int>> g[N];

bool haveKey[N];
bool used[N];

vector<int> edges[N];

int BFS(int st) {
    for (int i = 0; i < n; i ++) {
        haveKey[i] = used[i] = false;
        edges[i].clear();
    }
    queue<int> q;
    q.push(st);
    used[st] = true;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        int k = r[v];
        if (!haveKey[k]) {
            haveKey[k] = true;
            for (int to : edges[k]) {
                if (!used[to]) {
                    used[to] = true;
                    q.push(to);
                }
            }
            edges[k].clear();
        }
        for (auto [to, c] : g[v]) {
            if (used[to]) continue;
            if (!haveKey[c]) {
                edges[c].push_back(to);
            }
            else {
                used[to] = true;
                q.push(to);
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n; i ++) res += used[i];
    return res;
}

vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
    r = R;
    n = R.size();
    int m = U.size();
    for (int i = 0; i < m; i ++) {
        g[U[i]].push_back({V[i], C[i]});
        g[V[i]].push_back({U[i], C[i]});
    }
    int min_p = n;
    vector<int> res;
    for (int i = 0; i < n; i ++) {
        res.push_back(BFS(i));
        min_p = min(min_p, res.back());
    }
    for (int i = 0; i < n; i ++) res[i] = (res[i] == min_p);
    return res;
}

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