Submission #590395

#	Time	Username	Problem	Language	Result	Execution time	Memory
590395		oleh1421	Keys (IOI21_keys)	C++17	20 / 100	3075 ms	70256 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 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;
    }
    while (!comp.empty()){
        for (auto u:comp){
            set<int>st;
            for (int v:u) st.insert(r[v]);
            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});
                }
            }
        }
        for (int i=0;i<n;i++){
            if (ind[i]==i && !used[i]){
                if (go[i].empty()){
                    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;
        comp.clear();
        for (int i:V){
//            cout<<"X "<<i<<endl;
            if (!used[i]){
                dfs1(i);
                for (int j:order) ind[j]=i;
                order.clear();
            }
        }
        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;
            go[ind[i]].push_back(i);
        }
        for (int i=0;i<n;i++){
            if (!go[i].empty()) 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:52:17: warning: unused variable 'cnt' [-Wunused-variable]
   52 |             int cnt=0;
      |                 ^~~

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