Submission #868863

#	Time	Username	Problem	Language	Result	Execution time	Memory
868863		abcvuitunggio	Keys (IOI21_keys)	C++17	100 / 100	926 ms	65108 KiB

keys

#include <bits/stdc++.h>
using namespace std;
vector <int> ans,col[300001],ve;
vector <pair <int, int>> ke[300001];
int n,m,p[300001],d[300001],r[300001],isleaf[300001],exist[300001];
queue <int> q;
int f(int i){
    return (p[i]==i?i:p[i]=f(p[i]));
}
void unite(int i, int j){
    p[f(j)]=f(i);
}
int bfs(int s){
    q.push(s);
    d[s]=1;
    int res=-1;
    ve.clear();
    while (!q.empty()){
        int u=q.front();
        q.pop();
        if (f(u)!=f(s)){
            res=u;
            break;
        }
        ve.push_back(u);
        for (auto [v,c]:ke[u]){
            if (d[v])
                continue;
            if (exist[c]){
                d[v]=1;
                q.push(v);
                continue;
            }
            col[c].push_back(v);
        }
        for (int v:col[r[u]])
            if (!d[v]){
                d[v]=1;
                q.push(v);
            }
        col[r[u]].clear();
        exist[r[u]]=1;
    }
    for (int i:ve){
        d[i]=0;
        for (auto [v,c]:ke[i])
            col[c].clear();
        exist[r[i]]=0;
    }
    while (!q.empty()){
        d[q.front()]=0;
        ve.push_back(q.front());
        q.pop();
    }
    if (res!=-1)
        d[res]=0;
    return res;
}
vector <int> find_reachable(vector <int> R, vector <int> u, vector <int> v, vector <int> c){
    n=R.size();
    m=u.size();
    for (int i=0;i<n;i++){
        r[i]=R[i];
        p[i]=i;
        ans.push_back(0);
    }
    for (int i=0;i<m;i++){
        ke[u[i]].push_back({v[i],c[i]});
        ke[v[i]].push_back({u[i],c[i]});
    }
    bool ch=true;
    vector <pair <int, int>> tmp;
    while (ch){
        ch=false;
        tmp.clear();
        for (int i=0;i<n;i++)
            if (f(i)==i&&!isleaf[i]){
                int j=bfs(i);
                if (j==-1)
                    isleaf[i]=1;
                else{
                    tmp.push_back({j,i});
                    ch=true;
                }
            }
        for (auto [u,v]:tmp)
            unite(u,v);
    }
    int mn=1e9;
    for (int i=0;i<n;i++){
        if (i==f(i)){
            assert(bfs(i)==-1);
            mn=min(mn,(int)ve.size());
        }
    }
    for (int i=0;i<n;i++)
        if (i==f(i)){
            bfs(i);
            if (ve.size()==mn)
                for (int j:ve)
                    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:99:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |             if (ve.size()==mn)
      |                 ~~~~~~~~~^~~~
keys.cpp:96:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   96 |     for (int i=0;i<n;i++)
      |     ^~~
keys.cpp:103:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  103 |  return ans;
      |  ^~~~~~

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