Submission #995715

#	Time	Username	Problem	Language	Result	Execution time	Memory
995715		dimashhh	Keys (IOI21_keys)	C++17	100 / 100	1059 ms	139528 KiB

keys

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

const int N = 3e5 + 10;

int n,c[N],p[N],m;
vector<pair<int,int>> g[N];
vector<int> G[N],GR[N];
int get(int v){
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
bool bad[N];
vector<int> ans;
vector<int> pars;
vector<pair<int,int>> st[N];
int vis[N],timer = 1,vis2[N],edges_size = 0;
// pair<int,int> edges[N * 4];
vector<pair<int,int>> edges;
void solve(int tim){
    for(int cl = 0;cl < 18;cl++){
        vector<int> nv;
        vector<pair<int,int>> bb;
        for(int i:pars){
            if(bad[i]) continue;
            if(i != get(i)) continue;
            queue<int> add;
            add.push(i);
            timer++;
            vector<int>all;
            vis[i] = timer;
            while(!add.empty()){
                int v = add.front();
                vis2[c[v]] = timer;
                add.pop();
                for(auto [to,w]:g[v]){
                    if(get(to) == i && vis[to] != timer){
                        if(vis2[w] == timer){
                            vis[to] = timer;
                            G[v].push_back(to);
                            edges.push_back({v,to});
                            add.push(to);
                        }else{
                            all.push_back(w);
                            st[w].push_back({v,to});
                        }
                    }
                }
                for(auto [u,t]:st[c[v]]){
                    if(vis[t] != timer) add.push(t);
                    vis[t] = timer;
                    G[u].push_back(t);
                    edges.push_back({u,t});
                }
                st[c[v]].clear();
            }
            timer++;
            vis[i] = timer;
            queue<int> q;
            q.push(i);
            bool found = false;
            while(!q.empty()){
                int v = q.front();q.pop();
                for(int to:G[v]){
                    if(vis[to] == timer) continue;
                    vis[to] = timer;
                    q.push(to);
                }
                for(auto [to,w]:g[v]){
                    if(get(v) != get(to) && vis2[w] == timer - 1){
                        bb.push_back({v,to});
                        found = true;
                        break;
                    }
                }
                if(found) break;
            }
            if(!found){
                bad[i] = 1;
            }else{
                nv.push_back(i);
            }
        }
        for(auto [v,to]:bb){
            p[get(v)] = get(to);
            G[v].push_back(to);
            edges.push_back({v,to});
        }
        pars.swap(nv);
    }
}
int comp[N],sz[N];
vector<int> ord;
void dfs(int v){
    vis[v] = timer;
    for(int to:G[v]){
        if(vis[to] == timer) continue;
        dfs(to);
    }
    ord.push_back(v);
}
void dfs1(int v){
    for(int to:GR[v]){
        if(!comp[to]){
            sz[comp[v]]++;
            comp[to] = comp[v];
            dfs1(to);
        }
    }
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> C){
    n = (int)r.size();m = (int)v.size();
    ans.assign(n,0);
    for(int i = 0;i < n;i++){
        c[i] = r[i];
        p[i] = i;
        pars.push_back(i);
    }
    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]});
    }
    solve(0);
    for(int i = 0;i < n;i++){
        g[i].clear();
    }
    timer++;
    for(int i = 0;i < n;i++){
        if(vis[i] != timer){
            dfs(i);
        }
    }
    reverse(ord.begin(),ord.end());
    for(int i = 0;i < n;i++){
        G[i].clear();
    }
    for(auto [x,y]:edges){
        GR[y].push_back(x);
    }
    int t = 0;
    for(int i:ord){
        if(!comp[i]){
            comp[i] = ++t;
            sz[comp[i]] = 1;
            dfs1(i);
        }
    }
    timer++;
    for(auto [x,y]:edges){
        if(comp[x] != comp[y]){
            vis[comp[x]] = timer;
        }
    }
    int mn = 1e9;
    for(int i = 1;i <= t;i++){
        if(vis[i] == timer) continue;
        mn = min(mn,sz[i]);
    }
    for(int i = 0;i < n;i++){
        if(vis[comp[i]] != timer && sz[comp[i]] == mn){
            ans[i] = 1;
        }
    }
    return ans;
}

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