Submission #1042567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042567		ProtonDecay314	Keys (IOI21_keys)	C++17	100 / 100	2611 ms	58604 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--)

vvpi cant_visit;

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

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

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

        int find_root(int i) {
            return root[find(i)];
        }

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

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

            ncomps--;
        }
};

pi bfs_terminate_early(int n, int m, int s, const vi& r, const vvpi& adj, UF& uf, vb& vis) {

    set<int> found_k;
    vi to_delete;
    stack<int> to_unmark;

    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;
        to_unmark.push(i);

        if(uf.find_root(i) != s) {
            for(int k : to_delete) {
                cant_visit[k].clear();
            }
            while(!to_unmark.empty()) {
                vis[to_unmark.top()] = false;
                to_unmark.pop();
            }
            return {s, uf.find_root(i)};
        }

        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.pb(c);
            }
        }
    }

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

    while(!to_unmark.empty()) {
        vis[to_unmark.top()] = false;
        to_unmark.pop();
    }

    return {-1, -1};
}

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

    set<int> found_k;
    vi to_delete;

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

    stack<int> to_mark;

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

        q.pop();

        if(vis[i]) continue;
        vis[i] = true;
        to_mark.push(i);
        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]) {
            // cout << i << " " << j << " " << c << " " << s << "\n";
            if(vis[j]) continue;
            if(found_k.count(c) > 0) q.push({j, c});
            else {
                cant_visit[c].pb({j, c});
                to_delete.pb(c);
            }
        }
    }

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

    while(!to_mark.empty()) {
        ans[to_mark.top()] = num;
        to_mark.pop();
    }

    return num;
}

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

    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]});
    }

    UF uf(n);

    vb vis_bfs(n, false);

    // vb vis(n, false);

    for(int rep = 0; rep < 20; rep++) {
        vpi to_adjoin;

        // Do the BFS chuchu here
        for(int s = 0; s < n; s++) {
            if(uf.find_root(s) == s) {
                // vis[s] = true;
                auto [x, y] = bfs_terminate_early(n, m, s, r, adj, uf, vis_bfs);
                if(x != -1) {
                    to_adjoin.pb({x, y});
                }
            }
        }

        // Unify components

        for(auto [x, root] : to_adjoin) {
            uf.unify(x, root);
        }
    }

    // for(int i = 0; i < n; i++) {
    //     cout << uf.find_root(i) << " ";
    // }
    // cout << "\n";

    for(int s = 0; s < n; s++) {
        if(!vis_bfs[s] && uf.find_root(s) == s) {
            bfs(n, m, s, r, adj, vis_bfs, ans);
        }
    }

    int mn = INF(int);

    for(int i = 0; i < n; i++) {
        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: 30 / 30
• Subtask 5: 33 / 33