Submission #995625

#	Time	Username	Problem	Language	Result	Execution time	Memory
995625		dimashhh	Keys (IOI21_keys)	C++17	37 / 100	3079 ms	1083352 KiB

keys

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

#pragma GCC optimize("Ofast")
const int N = 1e6 + 1;

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]);
}
void merge(int a,int b){
    a = get(a);
    b = get(b);
    p[a] = b;
}
bool bad[N];
vector<int> ans;
vector<int> pars;
int vis[N],timer = 0,vis2[N];
vector<pair<int,int>> edges;
void solve(int tim){
    for(int i:pars){
        if(bad[i]) continue;
        set<int> add;
        add.insert(i);
        set<array<int,3>> bf;
        timer++;
        vis[i] = timer;
        while(!add.empty()){
            int v = (*add.begin());
            vis2[c[v]] = timer;
            add.erase(v);
            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);
                        GR[to].push_back(v);
                        edges.push_back({v,to});
                        add.insert(to);
                    }else{
                        bf.insert({w,v,to});
                    }
                }
            }
            auto it = bf.lower_bound({c[v],0,0});
            while(it != bf.end() && c[v] == (*it)[0]){
                int u = (*it)[1],t = (*it)[2];
                if(vis[t] != timer) add.insert((*it)[2]);
                vis[t] = timer;
                G[u].push_back(t);
                GR[t].push_back(u);
                edges.emplace_back(u,t);
                it = bf.erase(it);
            }
        }
        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){
                    p[get(v)] = get(to);
                    G[v].push_back(to);
                    GR[to].push_back(v);
                    edges.push_back({v,to});
                    found = true;
                    break;
                }
            }
            if(found) break;
        }
        if(!found){
            bad[i] = 1;
        }
    }
    pars.clear();
    for(int i = 0;i < n;i++){
        if(get(i) == i){
            pars.push_back(i);
        }
    }
}

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]});
    }
    for(int i = 0;i < 20;i++){
        solve(i);
    }
    timer++;
    for(int i = 0;i < n;i++){
        if(vis[i] != timer){
            dfs(i);
        }
    }
    reverse(ord.begin(),ord.end());
    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;
    vector<int> comps;
    for(int i = 1;i <= t;i++){
        if(vis[i] == timer) continue;
        if(sz[i] < mn){
            mn = sz[i];
            comps = vector<int> (1,i);
        }else if(sz[i] == mn){
            comps.push_back(i);
        }
    }
    timer++;
    for(int i:comps){
        vis[i] = timer;
    }
    for(int i = 0;i < n;i++){
        if(vis[comp[i]] == timer){
            ans[i] = 1;
        }
    }
    return ans;
}

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