제출 #1058842

#제출 시각아이디문제언어결과실행 시간메모리
1058842qwusha열쇠 (IOI21_keys)C++17
37 / 100
3030 ms174984 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second typedef long double ld; const ld eps = 1e-8; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); const ll inf = 1e18; const ll mod = 1e9 + 7; #include "keys.h" vector<set<int>> g; vector<vector<pair<int, int>>> gr; vector<int> num; int cnt = 0; void dfs(int v, int number) { num[v] = number; cnt++; for (auto u : g[v]) { if (num[u] == -1) { dfs(u, number); } } } vector<int> find_reachable(vector<int> r, vector<int> fir, vector<int>sec, vector<int> c) { bool first = 1; int n = r.size(); int m = fir.size(); for (int i = 0; i < m; i++) { if (c[i] != 0) first = 0; } if (1) { gr.resize(n); for (int i = 0; i < m; i++) { gr[fir[i]].push_back({sec[i], c[i]}); gr[sec[i]].push_back({fir[i], c[i]}); } vector<int> p(n); set<int> keys; set<int> pos; vector<int> used(n); vector<int> clear_used; set<int> clear_reach; vector<set<int>> reach(n); vector<set<int>> was_reached(n); int mini = n + 1; vector<int> nodes(n); for (int i = 0; i < n; i++) { nodes[i] = i; } random_device rd; mt19937 meow(rd()); shuffle(nodes.begin(), nodes.end(), meow); for (int j = 0; j < n; j++) { int i = nodes[j]; keys = {r[i]}; pos = {i}; for (auto ind : clear_used) used[ind] = 0; for (auto ind : clear_reach) reach[ind].clear(); clear_used.clear(); clear_reach.clear(); while (!pos.empty()) { auto v = *pos.begin(); pos.erase(pos.begin()); if (used[v]) continue; if (was_reached[i].find(v) != was_reached[i].end()) { p[i] = p[v]; break; } was_reached[v].insert(i); p[i]++; used[v] = 1; clear_used.push_back(v); if (p[i] > mini) { break; } if (keys.find(r[v]) == keys.end()) { keys.insert(r[v]); for (auto nod : reach[r[v]]) { if (!used[nod]) pos.insert(nod); } } for (auto [u, w] : gr[v]) { if (!used[u]) { if (keys.find(w) != keys.end()) { pos.insert(u); } else { reach[w].insert(u); clear_reach.insert(w); } } } } mini = min(mini, p[i]); } vector<int> res(n); for (int i = 0; i < n; i++) { if (p[i] == mini) res[i] = 1; } return res; } } /* int main() { vector<int> r = {0, 1, 1, 2, 2, 1, 2}, u = {0, 0, 1, 1, 2, 3, 3, 4, 4, 5}, v = {1, 2, 2, 3, 3, 4, 5, 5, 6, 6}, c = {0, 0, 1, 0, 0, 1, 2, 0, 2, 1}; auto res = find_reachable(r,u,v,c); for (int i = 0; i < r.size(); i++) { cout << res[i] << ' '; } } */

컴파일 시 표준 에러 (stderr) 메시지

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:31:10: warning: variable 'first' set but not used [-Wunused-but-set-variable]
   31 |     bool first = 1;
      |          ^~~~~
#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...