제출 #898826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898826		hazzle	열쇠 (IOI21_keys)	C++17	67 / 100	1051 ms	822624 KiB

keys

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;

template <typename T>
using prq = priority_queue <T>;

template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;

template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }

vec <int> find_reachable(vec <int> r, vec <int> u, vec <int> v, vec <int> c){
    int n = sz(r), m = sz(u);
    vec <vec <pii>> g(n);
    int mx_c = 0;
    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]});
        umax(mx_c, c[i]);
    }
    auto calc = [&](int s){
        unordered_map <int, bool> have, us;
        unordered_map <int, vec <int>> qu;
        vec <int> bfs = {s};
        us[s] = 1;
        for (int pt = 0; pt < sz(bfs); ++pt){
            int u = bfs[pt];
            have[r[u]] = 1;
            for (auto &v: qu[r[u]]) if (!us[v]){
                us[v] = 1;
                bfs.push_back(v);
            }
            qu[r[u]].clear();
            for (auto &[v, c]: g[u]) if (!us[v]){
                if (have[c]){
                    us[v] = 1;
                    bfs.push_back(v);
                }
                else{
                    qu[c].push_back(v);
                }
            }
        }
        return sz(bfs);
    };
    if (max(n, m) <= 2000){
        int mn = n + 42;
        vec <int> f(n);
        for (int s = 0; s < n; ++s){
            umin(mn, f[s] = calc(s));
        }
        vec <int> res(n);
        for (int i = 0; i < n; ++i){
            res[i] = (f[i] == mn);
        }
        return res;
    }
    else if (mx_c < 30){
        vec <int> msk(n);
        for (int i = 0; i < n; ++i){
            msk[i] = 1 << r[i];
        }
        auto sup = [&](int x, int y){
            return x == (x | y);
        };
        vec <tui> bfs;
        for (int u = 0; u < n; ++u){
            for (auto &[v, c]: g[u]){
                if (sup(msk[u], 1 << c)){
                    bfs.push_back({u, v, c});
                }
            }
        }
        for (int pt = 0; pt < sz(bfs); ++pt){
            auto [u, v, c] = bfs[pt];
            if (sup(msk[u], 1 << c) && !sup(msk[u], msk[v])){
                msk[u] |= msk[v];
                for (auto &[x, k]: g[u]){
                    if (sup(msk[u], 1 << k)){
                        bfs.push_back({u, x, k});
                    }
                    if (sup(msk[x], 1 << k)){
                        bfs.push_back({x, u, k});
                    }
                }
            }
        }
        vec <vec <int>> gg(n), dd(n);
        for (int u = 0; u < n; ++u){
            for (auto &[v, c]: g[u]){
                if (sup(msk[u], 1 << c)){
                    gg[u].push_back(v);
                    dd[v].push_back(u);
                }
            }
        }
        vec <bool> us(n);
        vec <int> top;
        auto dfs = [&](auto &&dfs, int u) -> void{
            us[u] = 1;
            for (auto &v: gg[u]){
                if (!us[v]) dfs(dfs, v);
            }
            top.push_back(u);
        };
        for (int i = 0; i < n; ++i){
            if (!us[i]) dfs(dfs, i);
        }
        reverse(all(top));
        fill(all(us), 0);
        vec <int> cmp(n);
        int z = 0;
        auto col = [&](auto &&col, int u) -> void{
            us[u] = 1;
            cmp[u] = z;
            for (auto &v: dd[u]){
                if (!us[v]) col(col, v);
            }
        };
        for (auto &u: top) if (!us[u]){
            col(col, u), ++z;
        }
        vec <int> deg(z);
        for (int u = 0; u < n; ++u){
            for (auto &v: gg[u]){
                if (cmp[u] != cmp[v]){
                    ++deg[cmp[u]];
                }
            }
        }
        vec <int> _f(z, 1e9), f(n, 1e9);
        for (int i = 0; i < n; ++i){
            if (_f[cmp[i]] == 1e9 && !deg[cmp[i]]){
                _f[cmp[i]] = calc(i);
            }
        }
        int mn = 1e9;
        for (int i = 0; i < n; ++i){
            umin(mn, f[i] = _f[cmp[i]]);
        }
        vec <int> res(n);
        for (int i = 0; i < n; ++i){
            res[i] = (f[i] == mn);
        }
        return res;
    }
    return {};
}

inline int solve(){
    return 0;
}

inline void precalc(){}

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