제출 #1219087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219087		brinton	Keys (IOI21_keys)	C++20	0 / 100	0 ms	392 KiB

keys

#include <bits/stdc++.h>
// #include "grader.cpp"
using namespace std;

vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
    int N = R.size(),M = U.size();
    vector<int> lgid;
    int lgsz = N;
    lgid.resize(N);
    for(int i = 0;i < N;i++) lgid[i] = i;

    while(true){
        // create edges, key
        vector<int> key,lsz;
        key = lsz = vector<int>(lgsz,0);
        for(int i = 0;i < N;i++){
            key[lgid[i]] |= (1 << R[i]);
            lsz[lgid[i]]++;
        }
        vector<set<int>> edges(lgsz);
        for(int i = 0;i < M;i++){
            int u = lgid[U[i]],v = lgid[V[i]],c = C[i];
            if(u == v) continue;
            if(key[u] & (1 << c)) edges[u].insert(v);
            if(key[v] & (1 << c)) edges[v].insert(u);
        }
        
        
        // init;
        vector<int> tin,low,gid;
        tin = low = gid = vector<int>(lgsz,-1);
        stack<int> st;
        int gt,gsz;
        gt = gsz = 0;
        // scc
        function<void(int,int)> tarjan = [&](int cur,int par){
            tin[cur] = low[cur] = gt++;
            st.push(cur);
            for(auto nxt:edges[cur]){
                if(gid[nxt] != -1) continue;
                if(tin[nxt] != -1) {
                    low[cur] = min(low[cur],low[nxt]);
                    continue;
                }

                tarjan(nxt,cur);
                if(low[nxt] > tin[cur]){
                    vector<int> gm;
                    while(st.top() != cur){
                        gm.push_back(st.top());
                        st.pop();
                    }
                    for(auto &i:gm) gid[i] = gsz;
                    gsz++;
                }
                low[cur] = min(low[cur],low[nxt]);
            }
        };
        for(int i = 0;i < N;i++){
            if(tin[i] == -1) {
                tarjan(i,-1);
                vector<int> gm;
                while(!st.empty()){
                    gm.push_back(st.top());
                    st.pop();
                }
                for(auto &i:gm) gid[i] = gsz;
                gsz++;
            }
        }

        if(gsz == lgsz) {
            // find the solution;
            int minsz = INT_MAX;
            for(int i = 0;i < lgsz;i++){
                if(edges[i].size() == 0){
                    minsz = min(minsz,lsz[i]);
                }
            }
            vector<int> ans(N,false);
            for(int i = 0;i < N;i++){
                int id = lgid[i];
                if(edges[id].size() == 0 && lsz[id] == minsz){
                    ans[i] = 1;
                }
            }
            return ans;
        }

        lgsz = gsz;
        for(auto &i:lgid) i = gid[i];
    }
    
}

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