Submission #1058563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058563		vjudge1	Keys (IOI21_keys)	C++17	37 / 100	3073 ms	25148 KiB

keys

#include <vector>

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

int search(int n, int s, vi &r, vector<vector<ii>> &L) {
    vi viz(n, 0);

    set<int> ToVisit, Chei;
    ToVisit.insert(s);
    vector<vi> Locked(n); /// daca as avea cheia i, le-as putea vizita
    Chei.insert(r[s]);

    viz[s] = 1;
    while(!ToVisit.empty()) {
        auto u = *ToVisit.begin();
        ToVisit.erase(u);
        int c = r[u];
        if(!Chei.count(c)) {
            Chei.insert(c);
            for(auto it2 : Locked[c]) {
                if(!viz[it2]) {
                    ToVisit.insert(it2);
                    viz[it2] = 1;
                }
            }
            Locked[c].clear();
        }
        for(auto [it, cul] : L[u]) {
            if(viz[it]) continue;
            if(Chei.count(cul)) {
                viz[it] = 1;
                ToVisit.insert(it);
            } else {
                Locked[cul].push_back(it);
            }
        }
    }
    int re = 0;
    for(auto it : viz) re += it;
    return re;
}

vi find_reachable(vi r, vi u, vi v, vi c) {
    int n = r.size(), m = u.size();
    vector<vector<ii>> L(n);
    for(int i = 0; i < m; ++i) {
        L[u[i]].push_back({v[i], c[i]});
        L[v[i]].push_back({u[i], c[i]});
    }
    vi ans(n, 0), re(n, 0);
    for(int i = 0; i < n; ++i)
        ans[i] = search(n, i, r, L);
    int mi = ans[0];
    for(auto it : ans) mi = min(mi, it);
    for(int i = 0; i < n; ++i)
        re[i] = (ans[i] == mi);
    return re;
}

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