Submission #527577

#	Time	Username	Problem	Language	Result	Execution time	Memory
527577		Deepesson	Keys (IOI21_keys)	C++17	100 / 100	2597 ms	122868 KiB

keys

#include <bits/stdc++.h>
#define MAX 305000
int N,M;
int chaves[MAX];
typedef std::pair<int,int> pii;
std::vector<pii> total[MAX];
std::vector<pii> con[MAX],rev[MAX];
bool vis1[MAX],vis2[MAX];
void conecta(int a,int b,int c){
    con[a].push_back({b,c});
    rev[b].push_back({a,c});
}
void limpar(void){
    for(int i=0;i!=MAX;++i){
        con[i].clear();
        rev[i].clear();
        vis1[i]=vis2[i]=0;
    }
}
std::vector<int> vec;
void dfs1(int pos){
    if(vis1[pos])return;
    vis1[pos]=true;
    for(auto&x:con[pos]){
        dfs1(x.first);
    }
    vec.push_back(pos);
}
std::vector<int> ans;
void dfs2(int pos){
    if(vis2[pos])return;
    vis2[pos]=true;
    for(auto&x:rev[pos]){
        dfs2(x.first);
    }
    ans.push_back(pos);
}
std::vector<std::vector<int>> SCC(void){
    for(int i=0;i!=N;++i){
        if(!vis1[i])dfs1(i);
    }
    std::vector<std::vector<int>> resp;
    while(vec.size()){
        int u = vec.back();
        vec.pop_back();
        if(vis2[u])continue;
        dfs2(u);
        resp.push_back(ans);
        ans.clear();
    }
    return resp;
}
void Decompor(std::vector<std::vector<int>> k){
    limpar();
    for(auto&x:k){
        std::map<int,bool> keys;
        for(auto&y:x){
            keys[chaves[y]]=true;
        }
        for(auto&y:x){
            for(auto&z:total[y]){
                if(z.second==-1||keys.find(z.second)!=keys.end()){
                    conecta(y,z.first,z.second);
                }
            }
        }
    }
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    N = r.size();
    for(int i=0;i!=N;++i){
        chaves[i]=r[i];
    }
    M = u.size();
    for(int i=0;i!=M;++i){
        total[u[i]].push_back({v[i],c[i]});
        total[v[i]].push_back({u[i],c[i]});
    }
    std::vector<std::vector<int>> prev;
    for(int i=0;i!=N;++i){
        std::vector<int> v;
        v.push_back(i);
        prev.push_back(v);
    }
    int val = 1e9,last=1e9;
    for(;;){
        Decompor(prev);
        std::vector<std::vector<int>> novo = SCC();
        int val = 1e9;
        for(auto&x:novo){
            std::map<int,bool> keys,possui;
            for(auto&y:x){
                keys[chaves[y]]=true;
                possui[y]=true;
            }
            for(auto&y:x){
                for(auto&z:total[y]){
                    if(z.second==-1||keys.find(z.second)!=keys.end()){
                        if(possui.find(z.first)==possui.end()){
                            goto proxs;
                        }
                    }
                }
                {
                    val=std::min(val,(int)x.size());
                }
                proxs:{}
            }
        }
        if(last==val)break;
        last=val;
        prev=novo;
    }
    std::vector<std::vector<int>> sobra;
    for(auto&x:prev){
        std::map<int,bool> keys,possui;
        for(auto&y:x){
            keys[chaves[y]]=true;
            possui[y]=true;
        }
        for(auto&y:x){
            for(auto&z:total[y]){
                if(z.second==-1||keys.find(z.second)!=keys.end()){
                    if(possui.find(z.first)==possui.end()){
                        goto proxa;
                    }
                }
            }
        }
        {
            sobra.push_back(x);
        }
        proxa:{}
    }
    std::vector<int> respfinal;
    for(int i=0;i!=N;++i)respfinal.push_back(0);
    std::vector<std::vector<int>> definitivo;
    int menor=1e9,total=0;
    for(auto&x:sobra){
        int p = x.size();
        if(menor>p){
            menor=p;
            definitivo.clear();
            definitivo.push_back(x);
        }else if(menor==p){
            definitivo.push_back(x);
        }
    }
    for(auto&x:definitivo)for(auto&y:x)respfinal[y]=1;
    return respfinal;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:85:9: warning: unused variable 'val' [-Wunused-variable]
   85 |     int val = 1e9,last=1e9;
      |         ^~~
keys.cpp:138:19: warning: unused variable 'total' [-Wunused-variable]
  138 |     int menor=1e9,total=0;
      |                   ^~~~~

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