Submission #790497

#	Time	Username	Problem	Language	Result	Execution time	Memory
790497		alexander707070	Keys (IOI21_keys)	C++17	100 / 100	1776 ms	128184 KiB

keys

#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;

int n,m,w[MAXN],dp[MAXN];
vector<int> v[MAXN],r[MAXN],sol;
bool li[MAXN],used[2*MAXN];
int k,comp[MAXN],br[MAXN],mins,out[MAXN];
unordered_set<int> keys[MAXN];
stack<int> st;

void dfs(int x){
    li[x]=true;
    for(int i=0;i<v[x].size();i++){
        if(!li[v[x][i]])dfs(v[x][i]);
    }
    st.push(x);
}

void scc(int x){
    li[x]=true; comp[x]=k;
    keys[k].insert(w[x]);

    for(int i=0;i<r[x].size();i++){
        if(!li[r[x][i]])scc(r[x][i]);
    }
}

vector<int> find_reachable(vector<int> R,vector<int> a,vector<int> b,vector<int> c){
    n=int(R.size()); m=int(c.size());

    for(int i=0;i<n;i++){
        w[i]=R[i];
        keys[i].insert(w[i]);
        comp[i]=i;
    }

    for(int test=0;test<10;test++){
        for(int i=0;i<m;i++){
            if(!used[2*i] and keys[comp[a[i]]].find(c[i])!=keys[comp[a[i]]].end()){
                v[a[i]].push_back(b[i]);
                r[b[i]].push_back(a[i]);
                used[2*i]=true;
            }

            if(!used[2*i+1] and keys[comp[b[i]]].find(c[i])!=keys[comp[b[i]]].end()){
                v[b[i]].push_back(a[i]);
                r[a[i]].push_back(b[i]);
                used[2*i+1]=true;
            }
        }

        for(int i=0;i<n;i++)li[i]=false;

        k=0;
        for(int i=0;i<n;i++){
            if(!li[i])dfs(i);
        }

        for(int i=0;i<n;i++){
            li[i]=false; keys[i].clear();
        }

        while(!st.empty()){
            if(!li[st.top()]){
                scc(st.top()); k++;
            }
            st.pop();
        }
    }

    for(int i=0;i<n;i++)br[comp[i]]++;
    for(int i=0;i<m;i++){
        if(comp[a[i]]==comp[b[i]])continue;
        if(keys[comp[a[i]]].find(c[i])!=keys[comp[a[i]]].end()){
            out[comp[a[i]]]++;
        }

        if(keys[comp[b[i]]].find(c[i])!=keys[comp[b[i]]].end()){
            out[comp[b[i]]]++;
        }
    }

    mins=n;
    for(int i=0;i<k;i++){
        if(out[i]==0){
            mins=min(mins,br[i]);
        }
    }

    for(int i=0;i<n;i++){
        if(br[comp[i]]==mins and out[comp[i]]==0)sol.push_back(1);
        else sol.push_back(0);
    }

    return sol;
}

/*
int main(){

    //find_reachable({0, 1, 1, 2},{0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});

    find_reachable({0, 1, 1, 2, 2, 1, 2},
{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});

}
*/

Compilation message (stderr)

keys.cpp: In function 'void dfs(int)':
keys.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
keys.cpp: In function 'void scc(int)':
keys.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<r[x].size();i++){
      |                 ~^~~~~~~~~~~~

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