Submission #1073425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073425		Itamar	Keys (IOI21_keys)	C++17	20 / 100	764 ms	121416 KiB

keys

using namespace std;
#include <vector>
#define vi vector<int>
#include <map>
#include<set>
#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;

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((fin[a]>0) && (fin[b]>0))return;
    if(fin[a]){
        kil(b);
        return;
    }
    if(fin[b]){
        kil(a);
        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);
    if(s.find(a)!=s.end()){
        s.erase(a);
        s.insert(b);
    }
    for(int i : col[a]){
        my[i]=b;
        col[b].push_back(i);
    }
}
int padf(int f){
    f=my[f];
    if(s.find(my[fun[f]]) == s.end() && fin[my[fun[f]]] == 0){
        fun[f] = padf(my[fun[f]]);
        return fun[f];
    }else return 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
        
        while(que[c].size()){
            int f = que[c].back();
            f=my[f];
            if(f == c){
                que[c].pop_back();
                continue;
            }
            if(fin[f]){
                k.push_back(c);
                fun[c]=c;
                break;
            }else if(s.find(f)!=s.end()){
                fun[c]=f;
                break;
            }else{
                f=padf(f);
                int m = my[fun[f]];
                if(fin[m]){
                    fun[c]=c;
                    k.push_back(c);
                    break;
                }
                if(m == c){
                    fun[c]=c;
                    popo.push_back(c);
                    co.push_back({f,c});
                    break;
                }else{
                    fun[c]=m;
                    break;
                }
            }

        }
        if(que[c].empty()){
            er.push_back(c);
            fin[c]=1;
            fun[c]=c;
            continue;
        }
    }

    map<int,int> deg;
    queue<int> q;
    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]];
        q.pop();
       // if(fin[fun[i]]){kil(i);continue;}
        deg[f]--;
        if(deg[f]==0)q.push(f);
    }
    vi erer;
    for(int i : s){
        if(deg[i])co.push_back({i,fun[i]});
        else erer.push_back(i);
    }
    for(int p : popo)que[p].pop_back();
    for(int e : er)s.erase(e);
    for(int e : erer)s.erase(e);
    for(int ki : k)kil(ki);
    for(auto[a,b]:co)con(a,b);
}

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);
        }
    }
    while(s.size()){
        iter();
    }
    vi ans(n);
    int mini = 1e9;
    for(int i = 0; i < n; i++){
        if(fin[i]==1)mini = min(mini,(int)col[i].size());
    }
    for(int i =0 ; i< n; i++){
        if(fin[i]==1){
            if(col[i].size() == mini){
                for(int j : col[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:152:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for(int i = 0; i < U.size(); i++){
      |                    ~~^~~~~~~~~~
keys.cpp:175:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  175 |             if(col[i].size() == mini){
      |                ~~~~~~~~~~~~~~^~~~~~~

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