Submission #802810

#	Time	Username	Problem	Language	Result	Execution time	Memory
802810		TheSahib	Keys (IOI21_keys)	C++17	67 / 100	3068 ms	59204 KiB

keys

#include <vector>
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>

using namespace std;

const int oo = 1e9 + 9;
const int MAX = 3e5 + 5;

struct edge{
    int v, u, c;
};

int n, m;
vector<edge> g[MAX];
int K[MAX];

vector<int> ans;
vector<bool> done(MAX, 0);
int mnAns = oo;

bool visited[MAX], hasKey[MAX];
vector<int> blockedList[MAX];

vector<int> keys, v, blocked;

void clear(){
    for(int a:v){
        visited[a] = 0;
    }
    for(int a:keys){
        hasKey[a] = 0;
    }
    for(auto a:blocked){
        vector<int> tmp;
        swap(blockedList[a], tmp);
    }
    blocked.clear();
    v.clear();
    keys.clear();


    vector<int> tmp1, tmp2, tmp3;
    swap(tmp1, blocked);
    swap(tmp2, keys);
    swap(tmp3, v);
}

queue<int> q;
int cnt = 1;
void add(int a){
    cnt++;
    q.push(a);
    visited[a] = 1;
    v.push_back(a);
}

int bfs(int start){
    queue<int> tmp;
    swap(tmp, q);
    
    cnt = 0;
    add(start);

    while(q.size()){
        int node = q.front();
        int k = K[node];
        q.pop();
        
        if(!hasKey[k]){
            hasKey[k] = 1;
            keys.push_back(k);
            for(int a:blockedList[k]){
                if(visited[a]) continue;
                if(done[a]) return oo;
                add(a);
            }
        }

        for(auto e:g[node]){
            if(visited[e.u]) continue;
            if(hasKey[e.c]){
                if(done[e.u]) return oo;
                add(e.u);
            }
            else{
                blocked.push_back(e.c);
                blockedList[e.c].push_back(e.u);
            }
        }
    }
    
    for(int a:v){
        ans[a] = min(ans[a], cnt);
    }
    return cnt;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    n = r.size();
    m = u.size();
    for (int i = 0; i < n; i++)
    {
        K[i] = r[i];
    }
    for (int i = 0; i < m; i++)
    {
        g[u[i]].push_back({u[i], v[i], c[i]});
        g[v[i]].push_back({v[i], u[i], c[i]});
    }
    ans.resize(n, oo);
    
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    srand(time(0));
    random_shuffle(order.begin(), order.end());

    for(int node:order){
        mnAns = min(mnAns, bfs(node));
        done[node] = 1;
        clear();
    }
    vector<int> cnt(n, 0);
    for (int i = 0; i < n; i++)
    {
        if(ans[i] == mnAns){
            cnt[i] = 1;
        }
    }
    return cnt;
}

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