제출 #1285290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285290		minhjulzi	열쇠 (IOI21_keys)	C++20	100 / 100	572 ms	53212 KiB

keys

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

#define task "task"
#define bit(x, i) ((x >> i) & 1)

// https://trap.jp/post/1224/
#define FOR1(i, a, b) for(int i = (a), _b = (b); i <= _b; i ++)
#define FOR2(i, a, b, c) for(int i = (a), _b = (b); i <= _b; i += c)
#define FORD1(i, a, b) for(int i = (a), _b = (b); i >= _b; i --)
#define FORD2(i, a, b, c) for(int i = (a), _b = (b); i >= _b; i -= c)
#define overload4(a, b, c, d, name, ...) name
#define FOR(...) overload4(__VA_ARGS__, FOR2, FOR1)(__VA_ARGS__)
#define FORD(...) overload4(__VA_ARGS__, FORD2, FORD1)(__VA_ARGS__)

#define pb emplace_back
#define pf emplace_front
#define ins emplace
#define mp make_pair
#define fi first
#define se second

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
// mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
// ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }
const int N = 3e5 + 5;
const int inf = 1e9;
const int mod = 1e9 + 7;
const int base = 31;
int sz = inf;
vi r, u, v, c, ans, vis, wait[N];
vector<bool> key, sus;
vector<pii> g[N];
struct DSU{
    int n, par[N];
    void init(int _n){
        n = _n;
        FOR(i, 0, n - 1) par[i] = i;
    }
    int get(int u){
        while(u != par[u]){ u = par[u] = par[par[u]]; }
        return u;
    }
    bool onion(int u, int v){
        u = get(u), v = get(v);
        if(u != v){
            par[v] = u;
            vis[u] = 1;
            return 1;
        }
        return 0;
    }
} dsu;
void bfs(int s){
    vi suscubus, waited, vis_key; queue<int> q;
    q.ins(s);
    bool check = 1;
    while(q.size()){
        int u = q.front(); q.pop();
        if(dsu.get(u) != s){
            dsu.onion(u, s);
            check = 0;
            break;
        }
        if(vis[u]) continue; vis[u] = 1;
        suscubus.pb(u);
        for(int v : wait[r[u]]) q.ins(v);
        wait[r[u]].clear();
        key[r[u]] = 1; vis_key.pb(r[u]);
        for(auto [v, w] : g[u])
            if(key[w]) q.ins(v);
            else{
                if(wait[w].empty()) waited.pb(w);
                wait[w].pb(v);
            }
    }
    for(int c : vis_key) key[c] = 0;
    for(int c : waited) wait[c].clear();
    if(check){
        if(sz == (int)suscubus.size()) for(int c : suscubus) ans.pb(c);
        if(sz > (int)suscubus.size()) ans = suscubus, sz = suscubus.size();
        sus[dsu.get(s)] = 1;
        for(int c : suscubus) vis[c] = 0;
    }
}
vector<int> find_reachable(vector<int> _r, vector<int> _u, vector<int> _v, vector<int> _c){
    r = _r, u = _u, v = _v, c = _c;
    int n = r.size(), m = c.size();
    sus.resize(n); key.resize(n);
    dsu.init(n);
    FOR(i, 0, m - 1){
        g[u[i]].pb(v[i], c[i]);
        g[v[i]].pb(u[i], c[i]);
    }
    while(1){
        vis.clear(), vis.resize(n);
        bool sex = 0;
        FOR(i, 0, n - 1) if(!vis[i] && !sus[dsu.get(i)]) bfs(i), sex = 1;
        if(!sex) break;
    }
    vector<int> res; res.resize(n);
    for(int c : ans) res[c] = 1;
    return res;
}
// void solve(){
//     // vector<int> a = find_reachable({0, 1, 1, 2}, {0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
//     vector<int> a = find_reachable({0, 1, 1, 2, 2, 1, 2}, {0, 0, 1, 1, 2, 3, 3, 4, 4, 5}, {1, 2, 2, 3, 3, 4, 5, 5, 6, 6}, {0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
//     for(int c : a) cout<<c<<" ";
// }
// signed main(){
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     if(fopen(task".inp", "r")){
//         freopen(task".inp", "r", stdin);
//         freopen(task".out", "w", stdout);
//     }
//     int nTest = 1;
//     // cin>>nTest;
//     while(nTest --) solve();
//     cerr << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
//     return 0;
// }

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