Submission #590411

#	Time	Username	Problem	Language	Result	Execution time	Memory
590411		oleh1421	Keys (IOI21_keys)	C++17	37 / 100	313 ms	67648 KiB

keys

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=500100;
vector<pair<int,int> >g[N];
vector<int>go[N];
vector<int>go1[N];
int ind[N];
int ind1[N];
int cnt[N];
bool used[N];
vector<int>order;
void dfs1(int v){
    used[v]=true;
    for (int to:go1[v]){
        if (!used[to]){
            dfs1(to);
        }
    }
    order.push_back(v);

}
void dfs(int v){
    used[v]=true;
    for (int to:go[v]){
        if (!used[to]){
            dfs(to);
        }
    }
    order.push_back(v);

}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int n=r.size();
    int m=u.size();
    for (int i=0;i<m;i++){
        g[u[i]].push_back({c[i],v[i]});
        g[v[i]].push_back({c[i],u[i]});
    }
    for (int i=0;i<n;i++){
        sort(g[i].begin(),g[i].end());
    }
    vector<pair<int,int> >ans;
    vector<vector<int> >comp;
    for (int i=0;i<n;i++){
        comp.push_back({i});
        ind[i]=i;
    }
    int Cnt=-1;
    while (!comp.empty()){
//        if ((int)comp.size()>Cnt) exit(1);
        Cnt++;
//        cout<<"IT\n";
        for (auto u:comp){
            set<int>st;
            for (int v:u) st.insert(r[v]);
//            for (int x:st) cout<<x<<" ";
//            cout<<endl;
            if (st.size()<Cnt) exit(1);
            int cnt=0;
            for (int v:u){
                for (auto [c,to]:g[v]){
                    if (st.find(c)==st.end()) continue;
                    if (ind[v]==ind[to] || ind[to]==-1) continue;
                    go[ind[v]].push_back(ind[to]);
                    go1[ind[to]].push_back(ind[v]);
                }

            }
            if (go[ind[u[0]]].empty()){
                for (int v:u){
                    ans.push_back({u.size(),v});
                }
            }
        }
        bool ok=false;
        for (int i=0;i<n;i++){
            if (ind[i]==i && !used[i]){
                if (go[i].empty()){
                    ok=true;
                    dfs1(i);
                }
            }
        }

        vector<int>V;
        for (int i=0;i<n;i++){
            if (ind[i]!=i) continue;
            if (!used[i]){
                V.push_back(i);
            }
        }
        for (int i=0;i<n;i++){
            if (ind[i]==-1) continue;
            if (used[ind[i]]) ind[i]=-1;
        }
        order.clear();
        for (int i:V){
            if (!used[i]) dfs(i);
        }
        reverse(order.begin(),order.end());
        V=order;
        order.clear();
        for (int i:V) used[i]=false;
        int last=comp.size();
        comp.clear();
        int cn=0;
        set<int>st;
        for (int i:V){
//            cout<<"X "<<i<<endl;
            if (!used[i]){
                dfs1(i);
                for (int j:order) ind1[j]=i;
                if (order.size()>1) ok=true;
                order.clear();
                cn++;
                st.insert(i);
            }
        }
        for (int i=0;i<n;i++){
            go[i].clear();
            go1[i].clear();
            cnt[i]=0;
            used[i]=false;
        }
        for (int i=0;i<n;i++){
            if (ind[i]==-1) continue;
            ind[i]=ind1[ind[i]];
            go[ind[i]].push_back(i);
        }
        for (int i=0;i<n;i++){
            if (!go[i].empty()) {
                if (st.find(i)==st.end()) exit(1);
                comp.push_back(go[i]);
            }
            go[i].clear();
        }
    }
    sort(ans.begin(),ans.end());
    while (!ans.empty() && ans[0].first<ans.back().first) ans.pop_back();
    vector<int>bt(n,0);
    for (auto cur:ans) bt[cur.second]=1;
	return bt;
}

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:59:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |             if (st.size()<Cnt) exit(1);
      |                 ~~~~~~~~~^~~~
keys.cpp:60:17: warning: unused variable 'cnt' [-Wunused-variable]
   60 |             int cnt=0;
      |                 ^~~
keys.cpp:76:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   76 |         bool ok=false;
      |              ^~
keys.cpp:105:13: warning: unused variable 'last' [-Wunused-variable]
  105 |         int last=comp.size();
      |             ^~~~

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