Submission #570805

#	Time	Username	Problem	Language	Result	Execution time	Memory
570805		doowey	Keys (IOI21_keys)	C++17	0 / 100	12 ms	21524 KiB

keys

#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;

int par[N];
vector<pii> T[N];
int col[N];
vector<int> vv[N];

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

void merge(int u, int v){
    u=fin(u);
    v=fin(v);
    if(u == v) return;
    par[u] = v;
}

bool vis[N];
bool has_key[N];
vector<int> nex[N];

vector<pii> unite;
vector<int> cols;
vector<int> nodes;

void clean(int a, int b){
    unite.push_back(mp(a, b));
    for(auto p : cols){
        has_key[p] = false;
        nex[p].clear();
    }
    cols.clear();
    nodes.clear();
}



void travel(int node){
    if(vis[node]) return;
    queue<int> lis;
    vis[node] = true;
    int init = node;
    while(!lis.empty()){

        node = lis.front();
        nodes.push_back(node);
        lis.pop();
        if(!has_key[col[node]]){
            cols.push_back(col[node]);
        }
        has_key[col[node]] = true;
        for(auto p : nex[col[node]]){
            if(vis[p]) continue;
            if(fin(p) != fin(node)){
                clean(node, p);
                return;
            }
        }
        nex[col[node]].clear();
        for(auto x : T[node]){
            if(vis[x.fi]) continue;
            if(has_key[x.se]){
                if(fin(x.fi) != fin(node)){
                    clean(node, x.fi);
                    return;
                }
                vis[x.fi]=true;
                lis.push(x.fi);
            }
            else{
                cols.push_back(x.se);
                nex[x.se].push_back(x.fi);
            }
        }
    }
    init=fin(init);
    vv[init]=nodes;

    for(auto p : cols){
        has_key[p] = false;
        nex[p].clear();
    }
    cols.clear();
    nodes.clear();
}


bool dd[N];
vector<int> yy;
void dfs(int u){
    dd[u]=true;
    yy.push_back(u);
    for(auto x : T[u]){
        if(dd[x.fi]) continue;
        dfs(x.fi);
    }
}


vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int m = u.size();
    int n = r.size();
    bool isnt = false;
    for(int i = 0 ; i < n; i ++ ){
        par[i] = i;
        col[i] = r[i];
        if(col[i] > 0) isnt = true;
    }
    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]));
    }
    int sz = n + 1;
    vector<int> oo;
    vector<int> cmp(n);
    for(int i = 0 ;i < n; i ++ ){
        if(dd[i]) continue;
        yy.clear();
        dfs(i);
        if(yy.size() < sz){
            sz = yy.size();
            oo = yy;
        }
        else if(yy.size() == sz){
            for(auto x : yy) oo.push_back(x);
        }
    }
    if(isnt){
        oo.clear();
        for(int i = 0 ; i < n; i ++ ){
            if(col[i] > 0) oo.push_back(i);
        }
    }
    for(auto v : oo) cmp[v] = true;
    bool changes = true;
    while(changes){
        changes = false;
        for(int i = 0 ; i < n; i ++ ){
            if(vis[i]) continue;
            if(par[i] == i){
                travel(i);
            }
        }
        for(auto x : unite){
            if(fin(x.fi) != fin(x.se)){
                merge(x.fi, x.se);
                changes = true;
            }
        }
        unite.clear();
        for(int i = 0 ; i < n; i ++ ){
            vis[i]=false;
        }
    }
    vector<int> ans(n);
    int reach = n + 1;
    vector<int> smol;
    int go;
    for(int i = 0 ; i < n; i ++ ){
        if(par[i] == i){
            travel(i);
            go = fin(i);
            if(vv[go].size() < reach){
                reach = vv[go].size();
                smol = vv[go];
            }
            else if(vv[go].size() == reach){
                for(auto x : vv[go]){
                    smol.push_back(x);
                }
            }
        }
    }
    for(auto x : smol){
        ans[x] = 1;
    }
    return cmp;
}

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:134:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  134 |         if(yy.size() < sz){
      |            ~~~~~~~~~~^~~~
keys.cpp:138:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  138 |         else if(yy.size() == sz){
      |                 ~~~~~~~~~~^~~~~
keys.cpp:177:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  177 |             if(vv[go].size() < reach){
      |                ~~~~~~~~~~~~~~^~~~~~~
keys.cpp:181:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  181 |             else if(vv[go].size() == reach){
      |                     ~~~~~~~~~~~~~~^~~~~~~~

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