Submission #827898

#	Time	Username	Problem	Language	Result	Execution time	Memory
827898		Liudas	Keys (IOI21_keys)	C++17	37 / 100	3067 ms	21008 KiB

keys

#include "keys.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>
#include <map>
#include <iostream>
using namespace std;
//DSU//
vector<int> par;
int find_par(int x){
    if(par[x] != x){
        par[x] = find_par(par[x]);
    }
    return par[x];
}
void merge(int a, int b){
    par[find_par(a)] = find_par(b);
}
//DSU//
vector<int> VIS, keys;
vector<vector<pair<int, int>>> tree;
vector<int> iter;
int ans = 1e9, it = 1;
vector<int> smol;
void BFS(int head){
    vector<int> been;
    vector<bool> vis(VIS.size()), got(VIS.size());
    map<int, vector<int>> locked;
    queue<int> que;
    que.push(head);
    got[keys[head]] = true;
    while(que.size()){
        int a = que.front();
        que.pop();
        if(find_par(head) != find_par(a)){
            merge(head, a);
            iter[find_par(a)] = it;
            return;
        }
        if(vis[a])continue;
        vis[a] = true;
        int key = keys[a];
        if(!got[key]){
            got[key] = true;
            for(int i : locked[key]){
                if(!vis[i]){
                    que.push(i);
                }
            }
        }
        for(auto [l, r] : tree[a]){
            if(got[r]){
                que.push(l);
            }
            else{
                locked[r].push_back(l);
            }
        }        
    }
    VIS[head] = true;
    int c = count(vis.begin(), vis.end(), true);
    if(ans > c){
        ans = c;
        smol.clear();
    }
    if(ans == c){
        for(int i = 0; i < vis.size(); i ++){
            if(vis[i]){
                smol.push_back(i);
            }
        }
    }
}
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C){
    int N = R.size(), M = C.size();
    par.assign(N, 0);
    VIS.assign(N, 0);
    keys.resize(N);
    tree.resize(N);
    iter.resize(N);
    for(int i = 0; i < N; i ++){
        keys[i] = R[i];
    }
    iota(par.begin(), par.end(), 0);
    for(int i = 0; i < M; i ++){
        tree[U[i]].push_back({V[i], C[i]});
        tree[V[i]].push_back({U[i], C[i]});
    }
    int check = 1;
    while(check){
        check = 0;
        for(int i = 0; i < N; i ++){
            if(find_par(i) == i && !VIS[i] && iter[i] != it){
                BFS(i);
                check = 1;
            }
        }
        it ++;
    }
    vector<int> ret(N);
    for(int i : smol){
        ret[i] = 1;
    }
    return ret;
}

Compilation message (stderr)

keys.cpp: In function 'void BFS(int)':
keys.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int i = 0; i < vis.size(); i ++){
      |                        ~~^~~~~~~~~~~~

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