Submission #1073568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073568		Itamar	Keys (IOI21_keys)	C++17	0 / 100	7 ms	45536 KiB

keys

using namespace std;
#include <vector>
#define vi vector<int>
#include <map>
#include<set>
#include<algorithm>
#include<queue>
const int siz = 3e5+2;

int my[siz];
int fun[siz];
vi que[siz];
vi col[siz];
map<int,vi> locked[siz];
int fin[siz];
set<int> keys[siz];
set<int> s;
int n;
int root[siz];
void kil(int c){
    fin[c]=2;
    if(s.find(c)!=s.end())s.erase(c);
}
void con(int a, int b){
    
    a = my[a], b = my[b];
    if(a==b)return;
    if(col[a].size() > col[b].size())swap(a,b);

    for(int k : keys[a]){
        for(int l : locked[b][k]){
            que[b].push_back(l);
        }
        locked[b][k].clear();
        keys[b].insert(k);
    }

    for(auto[l,v] : locked[a]){
        if(keys[b].find(l)!=keys[b].end()){
            for(int i : v)que[b].push_back(i);
        }else{
            for(int i : v)locked[b][l].push_back(i);
        }
    }

    for(int i : que[a])que[b].push_back(i);
    
    for(int i : col[a]){
        my[i]=b;
        col[b].push_back(i);
    }
}

void topo(map<int,int>& deg, int i){
        int f = my[fun[i]];
        deg[f]--;
        if(deg[f]==0)topo(deg,i);
}
int findr(int f){
    if(root[f]==f)return f;
    root[f] = findr(fun[f]);
    return root[f];
}
void iter(){
    vi k,er;
    vector<pair<int,int>> co;
    vi popo;
    for(int c : s){ // may be problematic because we kill stuff from s
        c=my[c];
        if(que[c].size()){
            fun[c]=que[c].back();
            

        }else fun[c]=c;
        
    }

    map<int,int> deg;
    queue<int> q;
    vi ord;
    for(int i : s)deg[my[fun[i]]]++;
    for(int i : s)if(deg[i]==0)q.push(i);
    while(!q.empty()){
        int i = q.front();
        int f = my[fun[i]];
        ord.push_back(i);
        q.pop();
        deg[f]--;
        if(deg[f]==0)q.push(f);
    }
    for(int i = 0; i < n; i++)if(deg[i])ord.push_back(i);
    reverse(ord.begin(),ord.end());
    for(int i =0; i < n; i++)if(deg[i])con(i,fun[i]);

    for(int i = 0; i < n; i++)if(deg[i])root[i]=my[i];
    for(int i = 0; i < n; i++)if(deg[i])fun[i]=my[i];
    for(int i:ord){
        root[i] = root[fun[i]];
    }
    for(int i = 0; i < n; i++){
        if(root[i]==i){

            while(que[i].size()){
                int f = que[i].back();
                que[i].pop_back();
                f=my[f];
                if(f!=i){
                    if(findr(f)==i){
                        while(f!=i){
                            con(f,fun[f]);
                            f=fun[f];
                        }
                    }else{
                        fun[i]=f;
                        break;
                    }
                }
            }
        }
    }
}

vi find_reachable(vi R, vi U,vi V,vi C){
    n = R.size();
    for(int i = 0; i < n; i++)fun[i]=i;
    for(int i = 0; i < n; i++){
        my[i]=i;
        col[i].push_back(i);
        keys[i].insert(R[i]);
        s.insert(i);
    }
    for(int i = 0; i < U.size(); i++){
        int a = U[i], b = V[i];
        if(*keys[a].begin() == C[i]){
            que[a].push_back(b);
        }else{
            locked[a][C[i]].push_back(b);
        }
        if(*keys[b].begin() == C[i]){
            que[b].push_back(a);
        }else{
            locked[b][C[i]].push_back(a);
        }
    }
        iter();
    
    vi ans(n);
    int mini = 1e9;
    for(int i = 0; i < n; i++){
        if(root[i]==i)mini = min(mini,(int)col[my[i]].size());
    }
    for(int i =0 ; i< n; i++){
        if(root[i]==i){
            if(col[my[i]].size() == mini){
                for(int j : col[my[i]])ans[j]=1;
            }
        }
    }
    return ans;
}

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:132:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int i = 0; i < U.size(); i++){
      |                    ~~^~~~~~~~~~
keys.cpp:154:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  154 |             if(col[my[i]].size() == mini){
      |                ~~~~~~~~~~~~~~~~~~^~~~~~~

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