Submission #827916

#	Time	Username	Problem	Language	Result	Execution time	Memory
827916		Liudas	Keys (IOI21_keys)	C++17	100 / 100	831 ms	66140 KiB

keys

#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>
#include <map>
using namespace std;

vector<int> par;
int find_par(int x){
    if(par[x] != x){
        par[x] = find_par(par[x]);
    }
    return par[x];
}
void merge(int a, int b){
    par[find_par(a)] = find_par(b);
}

vector<int> VIS, keys, iter, smol, been, lock;
vector<vector<pair<int, int>>> tree;
vector<bool> vis, got;
int ans = 1e9, it = 1;

void clean(){
    for(int i : been){
        got[keys[i]] = false;
        vis[i] = false;
    }
    been.clear();
}

void BFS(int head){
    queue<int> que;
    map<int, vector<int>> locked;
    que.push(head);
    got[keys[head]] = true;
    while(que.size()){
        int a = que.front();
        que.pop();
        if(find_par(head) != find_par(a)){
            merge(head, a);
            iter[find_par(a)] = it;
            clean();
            return;
        }
        if(vis[a])continue;
        vis[a] = true;
        been.push_back(a);
        int key = keys[a];
        if(!got[key]){
            got[key] = true;
            for(int i : locked[key]){
                que.push(i);
            }
        }
        for(auto [l, r] : tree[a]){
            if(got[r]){
                que.push(l);
            }
            else{
                locked[r].push_back(l);
            }
        }        
    }
    VIS[head] = true;
    int c = been.size();
    if(ans > c){
        ans = c;
        smol.clear();
    }
    if(ans == c){
        for(int i : been){
            smol.push_back(i);
        }
    }
    clean();
}
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C){
    int N = R.size(), M = C.size();
    par.assign(N, 0);
    VIS.assign(N, 0);
    iter.assign(N, 0);
    vis.assign(N, 0);
    got.assign(N, 0);
    keys.resize(N);
    tree.resize(N);
    iota(par.begin(), par.end(), 0);
    for(int i = 0; i < N; i ++){
        keys[i] = R[i];
    }
    for(int i = 0; i < M; i ++){
        tree[U[i]].push_back({V[i], C[i]});
        tree[V[i]].push_back({U[i], C[i]});
    }
    int check = 1;
    while(check){
        check = 0;
        for(int i = 0; i < N; i ++){
            if(find_par(i) == i && !VIS[i] && iter[i] != it){
                BFS(i);
                check = 1;
            }
        }
        it ++;
    }
    vector<int> ret(N);
    for(int i : smol)ret[i] = 1;
    return ret;
}

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