Submission #1061244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061244		TheQuantiX	Keys (IOI21_keys)	C++17	37 / 100	3095 ms	39104 KiB

keys

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll n, m, q, k, x, y, a, b, c;
vector< pair<ll, ll> > G[300000];
vector<int> key;

int rch(ll x) {
    map< ll, vector<ll> > mp1, mp2;
    set<ll> has;
    vector<bool> used(n);
    ll ans = 1;
    has.insert(key[x]);
    used[x] = 1;
    for (auto i : G[x]) {
        // if (x == 3) {
        //     cout << i.first << ' ' << i.second << '\n';
        // }
        if (used[i.first]) {
            continue;
        }
        if (has.count(i.second)) {
            mp1[i.second].push_back(i.first);
        }
        else {
            mp2[i.second].push_back(i.first);
        }
    }
    while (!mp1.empty()) {
        ll x = (*mp1.begin()).second[(*mp1.begin()).second.size() - 1];
        (*mp1.begin()).second.pop_back();
        if ((*mp1.begin()).second.empty()) {
            mp1.erase((*mp1.begin()).first);
        }
        if (used[x]) {
            continue;
        }
        ans++;
        used[x] = 1;
        if (!has.count(key[x]) && mp2.count(key[x])) {
            mp1[key[x]] = mp2[key[x]];
            mp2.erase(key[x]);
        }
        has.insert(key[x]);
        for (auto i : G[x]) {
            if (used[i.first]) {
                continue;
            }
            if (has.count(i.second)) {
                mp1[i.second].push_back(i.first);
            }
            else {
                mp2[i.second].push_back(i.first);
            }
        }
    }
    return ans;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    n = r.size();
    m = c.size();
    key = r;
    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]});
    }
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[i] = rch(i);
    }
    int mn = *min_element(ans.begin(), ans.end());
    for (int i = 0; i < n; i++) {
        if (ans[i] == mn) {
            ans[i] = 1;
        }
        else {
            ans[i] = 0;
        }
    }
    return ans;
}

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