제출 #1190075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190075		woohyun_jng	Keys (IOI21_keys)	C++20	100 / 100	733 ms	98316 KiB

keys

#include <bits/stdc++.h>
using namespace std;

typedef array<int, 2> pr;

const int MAX = 300001;

int parent[2][MAX], G[MAX], sz[MAX];

vector<int> arr[MAX];
set<pr> adj[MAX];
set<int> st[MAX];

int find(int T, int X) { return X == parent[T][X] ? X : parent[T][X] = find(T, parent[T][X]); } // 0 -> cycle 1 -> tree
void uni(int T, int X, int Y) {                                                                 // X를 Y 집합에 넣기
    X = find(T, X), Y = find(T, Y);
    if (X == Y)
        return;
    parent[T][X] = Y;
}

vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
    int N = R.size(), M = C.size(), X, Y, K, Z;
    vector<int> ans(N, 0);

    queue<int> q;
    set<pr>::iterator iter;

    for (int i = 0; i < M; i++) {
        if (R[U[i]] == C[i])
            arr[U[i]].push_back(V[i]);
        else
            adj[U[i]].insert({C[i], V[i]});

        if (R[V[i]] == C[i])
            arr[V[i]].push_back(U[i]);
        else
            adj[V[i]].insert({C[i], U[i]});
    }

    for (int i = 0; i < N; i++) {
        if (!arr[i].empty())
            G[i] = arr[i].back(), arr[i].pop_back();
        else
            G[i] = i;
        q.push(i), st[i].insert(R[i]), sz[i] = 1;
        parent[0][i] = i, parent[1][i] = i;
    }

    while (!q.empty()) {
        K = q.front(), q.pop();
        if (K == G[K])
            continue;

        if (find(1, G[K]) != find(1, K))
            uni(1, K, G[K]);
        else {
            X = G[K];
            while (X != K) {
                if (sz[X] > sz[K])
                    swap(st[X], st[K]), swap(adj[X], adj[K]), swap(arr[X], arr[K]);

                for (int i : st[X]) {
                    if (st[K].find(i) != st[K].end())
                        continue;
                    iter = adj[K].lower_bound({i, 0});
                    while (iter != adj[K].end() && (*iter)[0] == i)
                        arr[X].push_back((*iter)[1]), iter = adj[K].erase(iter);
                    st[K].insert(i);
                }

                for (pr i : adj[X]) {
                    if (st[K].find(i[0]) != st[K].end())
                        arr[K].push_back(i[1]);
                    else
                        adj[K].insert(i);
                }

                for (int i : arr[X])
                    arr[K].push_back(i);

                st[X].clear(), adj[X].clear(), arr[X].clear(), sz[K] += sz[X], sz[X] = 0;

                uni(0, X, K), Y = G[X], G[X] = K;
                st[X].clear(), X = Y;
            }

            while (!arr[K].empty() && find(0, arr[K].back()) == K)
                arr[K].pop_back();

            if (!arr[K].empty())
                G[K] = arr[K].back(), arr[K].pop_back();
            else
                G[K] = K;

            q.push(K);
        }
    }

    set<int> mn;

    X = MAX;
    for (int i = 0; i < N; i++) {
        if (i == find(0, i) && i == find(1, i) && sz[i] < X)
            X = min(X, sz[i]), mn.clear(), mn.insert(i);
        else if (i == find(0, i) && i == find(1, i) && sz[i] == X)
            mn.insert(find(0, i));
    }

    for (int i = 0; i < N; i++)
        ans[i] = mn.find(find(0, i)) != mn.end();

    return ans;
}

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