Submission #827907

#TimeUsernameProblemLanguageResultExecution timeMemory
827907LiudasKeys (IOI21_keys)C++17
0 / 100
0 ms340 KiB
#include "keys.h" #include <cassert> #include <cstdio> #include <vector> #include <queue> #include <algorithm> #include <numeric> #include <unordered_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<vector<int>> locked; vector<int> iter; int ans = 1e9, it = 1; vector<int> smol; vector<int> been, lock; vector<bool> vis, got; void clean(){ for(int i : been){ got[keys[i]] = false; } for(int i : lock){ locked[i].clear(); } lock.clear(); been.clear(); } void BFS(int head){ 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; clean(); return; } if(vis[a])continue; vis[a] = true; been.push_back(a); 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{ lock.push_back(r); locked[r].push_back(l); } } } VIS[head] = true; int c = been.size(); 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); } } } clean(); } vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C){ int N = R.size(), M = C.size(); locked.resize(N); par.assign(N, 0); VIS.assign(N, 0); keys.resize(N); tree.resize(N); iter.assign(N, 0); vis.assign(N, 0); got.assign(N, 0); 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; fill(vis.begin(), vis.end(), false); 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:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int i = 0; i < vis.size(); i ++){
      |                        ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...