Submission #1042512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042512		ProtonDecay314	Keys (IOI21_keys)	C++17	37 / 100	3032 ms	27916 KiB

keys

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

// class UF {
//     public:
//         int n;
//         int ncomps;
//         vi par;
//         vi csize;

//         UF(int a_n): n(a_n), ncomps(a_n), par(a_n, 0), csize(a_n, 1) {
//             for(int i = 0; i < n; i++) par[i] = i;
//         }

//         int find(int i) {
//             return (i == par[i] ? i : par[i] = find(par[i]));
//         }

//         int conn(int i, int j) {
//             return find(i) == find(j);
//         }

//         void unify(int i, int j) {
//             int pari = find(i), parj = find(j);
//             if(pari == parj) return;
//             if(csize[pari] < csize[parj]) {
//                 par[pari] = parj;
//                 csize[parj] += csize[pari];
//             } else {
//                 par[parj] = pari;
//                 csize[pari] += csize[parj];
//             }

//             ncomps--;
//         }
// }
vvpi cant_visit;

int bfs(int n, int m, int s, const vi& r, const vvpi& adj) {
    int num = 0;

    set<int> found_k;
    set<int> to_delete;
    vb vis(n, false);

    queue<pi> q;
    q.push({s, r[s]});

    while(!q.empty()) {
        auto [i, cr] = q.front();

        q.pop();

        if(vis[i]) continue;
        vis[i] = true;
        num++;

        if(found_k.count(r[i]) == 0) {
            while(cant_visit[r[i]].size() > 0) {
                q.push(cant_visit[r[i]].back());
                cant_visit[r[i]].pop_back();
            }
            found_k.insert(r[i]);
            to_delete.erase(r[i]);
        }

        for(auto [j, c] : adj[i]) {
            if(vis[j]) continue;
            if(found_k.count(c) > 0) q.push({j, c});
            else {
                cant_visit[c].pb({j, c});
                to_delete.insert(c);
            }
        }
    }

    for(int k : to_delete) {
        cant_visit[k].clear();
    }

    return num;
}

vi find_reachable(vi r, vi u, vi v, vi c) {
    int n = r.size(), m = u.size();
	vi ans(n, 1);

    vvpi adj;
    for(int i = 0; i < n; i++) {
        vpi adjr;
        adj.pb(adjr);
    }

    for(int i = 0; i < n; i++) {
        vpi cant_visitr;
        cant_visit.pb(cant_visitr);
    }

    for(int i = 0; i < m; i++) {
        adj[u[i]].pb({v[i], c[i]});
        adj[v[i]].pb({u[i], c[i]});
    }

    int mn = INF(int);

    for(int i = 0; i < n; i++) {
        ans[i] = bfs(n, m, i, r, adj);
        mn = min(mn, ans[i]);
    }

    for(int i = 0; i < n; i++) {
        ans[i] = (ans[i] == mn ? 1 : 0);
    }

	return ans;
}

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