Submission #802790

#	Time	Username	Problem	Language	Result	Execution time	Memory
802790		TheSahib	Keys (IOI21_keys)	C++17	9 / 100	325 ms	41108 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;
set<int> 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();

    set<int> tmp1;
    swap(tmp1, blocked);

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

int bfs(int start){
    queue<int> q;
    q.push(start);
    v.push_back(start);
    visited[start] = 1;

    int cnt = 1;
    while(q.size()){
        int node = q.front();
        int k = K[node];
        q.pop();
        
        if(!hasKey[k]){
            blocked.erase(k);
            hasKey[k] = 1;
            keys.push_back(k);
            for(int a:blockedList[k]){
                if(visited[a]) continue;
                cnt++;
                if(done[a]){
                    return oo;
                }
                visited[a] = 1;
                v.push_back(a);
                q.push(a);
            }
            vector<int> tmp;
            swap(blockedList[k], tmp);
        }

        for(auto e:g[node]){
            if(visited[e.u]) continue;
            if(hasKey[e.c]){
                cnt++;
                if(done[e.u]){
                    return oo;
                }
                visited[e.u] = 1;
                v.push_back(e.u);
                q.push(e.u);
            }
            else{
                blocked.insert(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);
    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: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33