Submission #802906

#	Time	Username	Problem	Language	Result	Execution time	Memory
802906		TheSahib	Keys (IOI21_keys)	C++17	100 / 100	972 ms	52552 KiB

keys

#pragma GCC optimize("O3")

#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];

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

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

vector<int> v, blocked;

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

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

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

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;
            for(int a:blockedList[k]){
                if(visited[a]) continue;
                if(done[a] || !add(a)) return oo;
            }
        }

        for(auto& e:g[node]){
            if(visited[e.u]) continue;
            if(hasKey[e.c]){
                if(done[e.u] || !add(e.u)) return oo;
            }
            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) {
    v.reserve(MAX);
    blocked.reserve(MAX);

    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]});
    }
    for (int i = 0; i < n; i++)
    {
        random_shuffle(g[i].begin(), g[i].end());
    }
    
    fill(ans, ans + MAX, oo);

    vector<int> p(2 * m);
    for (int i = 0; i < m; i++)
    {
        p[2 * i] = u[i];
        p[2 * i + 1] = v[i];
    }
    random_shuffle(p.begin(), p.end());
    random_shuffle(p.begin(), p.end());
    random_shuffle(p.begin(), p.end());
    for (int node : p)
    {
        if(done[node]) continue;
        mnAns = min(mnAns, bfs(node));
        done[node] = 1;
        clear();
    }
    for (int node = 0; node < n; node++)
    {
        if(done[node]) continue;
        mnAns = min(mnAns, bfs(node));
        done[node] = 1;
        clear();
    }
    vector<int> cnt(n, 0);
    for (int i = 0; i < n; i++)
    {
        cnt[i] = (ans[i] == mnAns);
    }
    return cnt;
}

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