Submission #824030

#	Time	Username	Problem	Language	Result	Execution time	Memory
824030		PixelCat	Keys (IOI21_keys)	C++17	100 / 100	950 ms	142484 KiB

keys

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 300'000;

struct DSU {
    int p[MAXN + 10];
    int sz[MAXN + 10];
    void init() {
        memset(p, -1, sizeof(p));
        memset(sz, 0, sizeof(sz));
    }
    int find(int n) {
        if(p[n] < 0) return n;
        return p[n] = find(p[n]);
    }
    void uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return;
        p[b] = a;
        sz[a] += sz[b] + 1;
    }
    bool same(int a, int b) {
        return find(a) == find(b);
    }
    int size(int n) {
        return sz[find(n)] + 1;
    }
} dsu, big_dsu;

set<int> keys[MAXN + 10];
vector<int> edges[MAXN * 2 + 10];
unordered_map<int, int> locked[MAXN + 10];  // key -> vertices
vector<int> unlocked[MAXN + 10];
int ayaya[MAXN + 10];

// merge v2 into v1
void merge_vector(vector<int> &v1, vector<int> &v2) {
    if(sz(v1) < sz(v2)) v1.swap(v2);
    v1.insert(v1.end(), all(v2));
    v2.clear();
}

int merge_groups(int a, int b) {
    assert(dsu.find(a) == a && dsu.find(b) == b && a != b);
    // if(sz(keys[a]) + sz(locked[a]) < sz(keys[b]) + sz(locked[b])) swap(a, b);
    if(sz(keys[a]) + sz(locked[a]) < sz(keys[b]) + sz(locked[b])) {
        keys[a].swap(keys[b]);
        locked[a].swap(locked[b]);
    }
    // merge b into a

    // merge keys
    for(auto &k:keys[b]) if(!keys[a].count(k)) {
        if(locked[a].count(k)) {
            merge_vector(unlocked[a], edges[locked[a][k]]);
            locked[a].erase(k);
        }
        keys[a].insert(k);
    }
    keys[b].clear();

    // merge locked edges
    for(auto &it:locked[b]) {
        if(keys[a].count(it.F)) {
            merge_vector(unlocked[a], edges[it.S]);
        } else if(locked[a].count(it.F)) {
            merge_vector(edges[locked[a][it.F]], edges[it.S]);
        } else {
            locked[a][it.F] = it.S;
        }
    }
    locked[b].clear();

    // merge unlocked edges
    merge_vector(unlocked[a], unlocked[b]);

    dsu.uni(a, b);

    return a;
}

vector<i32> find_reachable(vector<i32> R, vector<i32> U, vector<i32> V, vector<i32> C) {
    int n = sz(R);
    int m = sz(C);

    For(i, 0, n - 1) {
        keys[i].insert(R[i]);
    }
    int ptr = 0;
    For(i, 0, m - 1) {
        int a = U[i], b = V[i], c = C[i];
        if(R[a] == c) {
            unlocked[a].eb(b);
        } else {
            if(!locked[a].count(c)) locked[a][c] = (ptr++);
            edges[locked[a][c]].eb(b);
        }
        if(R[b] == c) {
            unlocked[b].eb(a);
        } else {
            if(!locked[b].count(c)) locked[b][c] = (ptr++);
            edges[locked[b][c]].eb(a);
        }
    }

    dsu.init();
    big_dsu.init();
    memset(ayaya, -1, sizeof(ayaya));
    For(start, 0, n - 1) {
        int cur = start;
        while(sz(unlocked[cur])) {
            int nxt = unlocked[cur].back();
            unlocked[cur].pop_back();
            nxt = dsu.find(nxt);
            if(cur == nxt) {
                ;
            } else if(!big_dsu.same(cur, nxt)) {
                ayaya[cur] = nxt;
                big_dsu.uni(cur, nxt);
                break;
            } else {
                vector<int> sus;
                while(nxt != cur) {
                    sus.eb(nxt);
                    nxt = dsu.find(ayaya[nxt]);
                }
                for(auto &i:sus) {
                    cur = merge_groups(cur, i);
                }
                ayaya[cur] = -1;
            }
        }
    }

    int mn = n * 8;
    For(i, 0, n - 1) if(dsu.find(i) == i && ayaya[i] == -1) {
        mn = min(mn, dsu.size(i));
    }
    
    // cerr << mn << "\n";
    // For(i, 0, n - 1) cerr << dsu.find(i) << " \n"[i == n - 1];
    // For(i, 0, n - 1) cerr << ayaya[i] << " \n"[i == n - 1];

    vector<int> ret(n);
    For(i, 0, n - 1) {
        int owo = dsu.find(i);
        if(ayaya[owo] == -1 && dsu.size(owo) == mn) {
            ret[i] = 1;
        } else {
            ret[i] = 0;
        }
    }
    return ret;
}

/*

4 5
0 1 1 2
0 1 0
0 2 0
1 2 1
1 3 0
3 1 2

0 1 1 0


7 10
0 1 1 2 2 1 2
0 1 0
0 2 0
1 2 1
1 3 0
2 3 0
3 4 1
3 5 2
4 5 0
4 6 2
5 6 1

0 1 1 0 1 0 1


3 1
0 0 0
0 1 0

0 0 1

*/

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