Submission #1073640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073640		Itamar	Keys (IOI21_keys)	C++17	100 / 100	1192 ms	269824 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];
set<int> keys[siz];
int n;
int root[siz];

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);
    }
}

int findr(int f){
    if(root[f]==f)return f;
    root[f] = findr(root[f]);
    return root[f];
}
int getfun(int i){
    int f =i;
    while(my[i]==my[f])f=fun[f];
    return f;
}
void iter(){
    for(int i = 0; i < n; i++)root[i]=i;
    for(int i = 0; i < n; i++)fun[i]=i;
    for(int i = 0; i < n; i++){
        if(findr(i)==i){
            while(que[my[i]].size()){
                int f = que[my[i]].back();
                que[my[i]].pop_back();
                
                    if(findr(f)==i){
                        while(my[f]!=my[i]){
                            int g = getfun(f);
                            con(f,g);
                            f=g;
                        }
                    }else{
                        root[i]=findr(f);
                        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]);
    }
    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:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i = 0; i < U.size(); i++){
      |                    ~~^~~~~~~~~~
keys.cpp:114:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |             if(col[my[i]].size() == mini){
      |                ~~~~~~~~~~~~~~~~~~^~~~~~~

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