Submission #802159

#	Time	Username	Problem	Language	Result	Execution time	Memory
802159		TheSahib	Keys (IOI21_keys)	C++17	37 / 100	3088 ms	57648 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;
int mnAns = n;

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

void bfs(int start){
    vector<int> keys, v;
    set<int> blocked;

    queue<int> q;
    q.push(start);
    int cnt = 0;
    while(q.size()){
        int node = q.front();
        int k = K[node];
        q.pop();
        if(visited[node]) continue;
        //cout << node << '\n';
        
        cnt += 1;
        if(cnt > mnAns){
            ans[start] = n + 1;
            break;
        }

        if(ans[node] != -1){
            if(ans[node] > mnAns){
                ans[start] = n + 1;
                break;
            }
            set<int>& s = st[reachable[node]];
            if(s.count(start)){
                ans[start] = ans[node];
                reachable[start] = reachable[node];
                break;
            }
            else{
                ans[start] = n + 1;
                break;
            }
        }

        visited[node] = 1;
        v.push_back(node);

        if(!hasKey[k]){
            blocked.erase(k);
            hasKey[k] = 1;
            keys.push_back(k);
            for(int a:blockedList[k]){
                q.push(a);
            }
            vector<int> tmp;
            swap(blockedList[k], tmp);
        }
        for(auto e:g[node]){
            if(hasKey[e.c]){
                q.push(e.u);
            }
            else{
                blocked.insert(e.c);
                blockedList[e.c].push_back(e.u);
            }
        }
    }
    for(int b:blocked){
        vector<int> tmp;
        swap(tmp, blockedList[b]);
    }
    for(int k:keys){
        hasKey[k] = 0;
    }
    for(int node:v){
        visited[node] = 0;
    }
    if(ans[start] == -1){
        ans[start] = cnt;
        reachable[start] = st.size();
        st.push_back(set<int>());
        set<int>& tmp = st.back();
        for(int a:v){
            tmp.insert(a);
        }
    }
    mnAns = min(mnAns, ans[start]);
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    n = r.size();
    mnAns = n;
    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]});
    }
    memset(reachable, -1, sizeof(reachable));
    ans.resize(n, -1);
    
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    random_shuffle(order.begin(), order.end());
    for(int node:order){
        //cout << node << ":\n";
        bfs(node);
    }
    vector<int> cnt(n, 0);
    for (int i = 0; i < n; i++)
    {
        //cout << ans[i] << ' ';
        if(ans[i] == mnAns){
            cnt[i] = 1;
        }
    }
    //cout << '\n';
    return cnt;
}

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