제출 #447130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447130		fun_day	Keys (IOI21_keys)	C++17	39 / 100	307 ms	37212 KiB

keys

#include <bits/stdc++.h>
/*
 basic idea: mask[i] stores all the keys you can possibly grab, starting at i
 initially, mask[i] = (1<<r[i]), you only have your own key
 the main body is done in the dfs function
 firstly, i grab all keys from my neighbors
 once i do so, i check my neighbors
 if any of my neighbors can gain a key from me
 i recursively pass this key over
 once we solve for mask[i] for all i
 it becomes a very simple directed graph
 time complexity O(mk)
*/
using namespace std;

const int N=300050;
vector<pair<int,int>> adj[N];

int mask[N];

void bfs(int z) {
    queue<int> q;
    q.push(z);
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        int mask_init;
        assert(x<N);
        do {
            mask_init = mask[x];
            for(auto p: adj[x]) {
                if((mask[x] & (1<<p.second))) {
                    mask[x] |= mask[p.first];
                }
            }
        } while(mask[x]!=mask_init);

        for(auto p: adj[x]) {
            if((mask[p.first] & (1<<p.second))!=0 and (mask[p.first]|mask[x])!=mask[p.first]) {
                mask[p.first] = (mask[p.first] | mask[x]);
                q.push(p.first);
            }
        }
    }
}

int pt[N];
int findset(int x) {
    while(pt[x]^x) {
        x = pt[x] = pt[pt[x]];
    }
    return x;
}
void unionset(int x, int y) {
    x = findset(x);
    y = findset(y);
    pt[x] = y;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int m = c.size();
    int n = r.size();
    for(int i=0; i<m; i++) {
        adj[u[i]].emplace_back(v[i], c[i]);
        adj[v[i]].emplace_back(u[i], c[i]);
    }
    for(int i=0; i<n; i++) {
        mask[i] = (1<<r[i]); // initialize the mask to your own key
    }

    for(int i=0; i<n; i++) {
        bfs(i);
    }
    for(int i=0; i<m; i++) {
        if(mask[u[i]] &(1<<c[i])) { // if u->v, then u's mask should be a supermask of v
            assert((mask[u[i]] | mask[v[i]]) == mask[u[i]]);
        }
        if(mask[v[i]] &(1<<c[i])) {
            assert((mask[u[i]] | mask[v[i]]) == mask[v[i]]);
        }
    }

    // n is the "dummy" node
    for(int i=0; i<=n; i++) {
        pt[i] = i;
    }

    for(int i=0; i<m; i++) {
        if(mask[u[i]] &(1<<c[i])) { // can pass through
            // case 1, different mask
            // then vertex u is "dead"
            if(mask[u[i]] != mask[v[i]]) {
                unionset(u[i], n);
            } else {
                // case 2: same mask
                // then they can inter-travel
                unionset(u[i], v[i]);
            }
        }
        if(mask[v[i]] &(1<<c[i])) { // can pass through
            // case 1, different mask
            // then vertex u is "dead"
            if(mask[u[i]] != mask[v[i]]) {
                unionset(v[i], n);
            } else {
                // case 2: same mask
                // then they can inter-travel
                unionset(u[i], v[i]);
            }
        }
    }
    // record down component sizes
    int component_size[n+1];
    for(int i=0; i<=n; i++) {
        component_size[i] = 0;
    }
    int smallest = n;
    for(int i=0; i<n; i++) {
        component_size[findset(i)]++;
    }


    for(int i=0; i<n; i++) {
        if(findset(i)!=findset(n)) { // is actually a sink scc
            smallest = min(smallest, component_size[findset(i)]);
        }
    }
    vector<int> ans(n);
    for(int i=0; i<n; i++) {
        if(findset(i) != findset(n) and component_size[findset(i)]==smallest) {
            ans[i] = 1;
        }
    }
    return ans;
}

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