Submission #570926

#	Time	Username	Problem	Language	Result	Execution time	Memory
570926		doowey	Keys (IOI21_keys)	C++17	100 / 100	1681 ms	62444 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair


const int N = (int)3e5 + 1;

vector<pii> T[N];
int col[N];
bool collect[N];
vector<int> st[N];
bool vis[N];

vector<int> nds;
vector<int> keys;

int par[N];

int fin(int u){
    if(par[u] == u) return u;
    return par[u]=fin(par[u]);
}

void unite(int ui, int vi){
    ui=fin(ui);
    vi=fin(vi);
    if(ui==vi) return;
    par[ui]=vi;
}

vector<pii> cc;

void clean(int xi, int yi){
    for(auto x : keys){
        collect[x] = false;
        st[x].clear();
    }
    cc.push_back(mp(xi, yi));
    keys.clear();
}


void travel(int node, bool mode){
    queue<int> que;
    que.push(node);
    vis[node]=true;
    int cur;

    while(!que.empty()){
        cur = que.front();
        que.pop();
        collect[col[cur]] = true;
        keys.push_back(col[cur]);
        nds.push_back(cur);
        for(auto x : T[cur]){
            if(vis[x.fi]) continue;
            if(mode)nds.push_back(x.fi);
            keys.push_back(x.se);
            if(collect[x.se]){
                if(fin(x.fi) != fin(node) && mode){
                    clean(node, x.fi); // f(x.fi) <= f(node)
                    return;
                }
                vis[x.fi]=true;
                que.push(x.fi);
            }
            else{
                st[x.se].push_back(x.fi);
            }
        }
        for(auto x : st[col[cur]]){
            if(vis[x]) continue;
            if(fin(x) != fin(node) && mode){
                clean(node, x);
                return;
            }
            vis[x] = true;
            que.push(x);
        }
        st[col[cur]].clear();
    }
    for(auto x : keys){
        collect[x]=false;
        st[x].clear();
    }
    keys.clear();
}


vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int m = u.size();
    int n = r.size();
    for(int i = 0 ; i < n; i ++ ){
        col[i] = r[i];
        par[i] = i;
    }
    for(int i = 0 ; i < m ; i ++ ){
        T[u[i]].push_back(mp(v[i], c[i]));
        T[v[i]].push_back(mp(u[i], c[i]));
    }
    for(int iter = 0; iter < 20; iter ++ ){
        for(int i = 0 ; i < n; i ++ ){
            if(vis[i]) continue;
            if(par[i] == i){
                travel(i, true);
                for(auto x : nds){
                    vis[x]=false;
                }
                nds.clear();
            }
        }
        for(int i = 0 ; i < n; i ++ ){
            vis[i]=false;
            collect[i]=false;
            st[i].clear();
        }
        for(auto x : cc){
            unite(x.fi, x.se);
        }
        cc.clear();
    }
    vector<int> sol(n);
    int sz = n + 1;
    vector<int> trav;
    for(int i = 0 ; i < n; i ++ ){
        if(par[i] == i){
            travel(i, false);
            if(nds.size() < sz){
                sz = nds.size();
                trav = nds;
            }
            else if(nds.size() == sz){
                for(auto x : nds){
                    trav.push_back(x);
                }
            }
            nds.clear();
        }
    }
    for(auto x : trav) sol[x] = 1;
    return sol;
}

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:136:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  136 |             if(nds.size() < sz){
      |                ~~~~~~~~~~~^~~~
keys.cpp:140:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |             else if(nds.size() == sz){
      |                     ~~~~~~~~~~~^~~~~

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