이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "keys.h"
#include <iostream>
#include <vector>
#include <set>
using namespace std;
using vi = vector<int>;
const int N = 300'005;
set<int>keys[N];
set<pair<int,int>>maybe[N];
vector<int>ac[N];
int tree[N];
int gtree(int x) { if (x == tree[x]) return x; return tree[x] = gtree(tree[x]); }
int cc[N];
int gcc(int x) { if (x == cc[x]) return x; return cc[x] = gcc(cc[x]); }
int par[N];
void add_edge(int x, int y) { tree[x] = par[x] = y; }
vector<pair<int,int>>del;
void unite(int x, int y) {
x = gcc(x), y = gcc(y);
if (x == y) return;
if (keys[x].size() + maybe[x].size() + ac[x].size() >
keys[y].size() + maybe[y].size() + ac[y].size()) swap(x, y);
cc[x] = y;
for (auto u : ac[x]) ac[y].emplace_back(u);
ac[x].clear();
for (auto u : keys[x]) {
if (keys[y].count(u)) continue;
auto it = maybe[y].lower_bound({u, -1});
while (it != maybe[y].end() && it->first == u) {
del.emplace_back(*it);
ac[y].emplace_back(it->second);
++it;
}
keys[y].insert(u);
}
for (auto i : del) maybe[y].erase(i); del.clear();
keys[x].clear();
for (auto it : maybe[x]) {
if (keys[y].count(it.first)) ac[y].emplace_back(it.second);
else maybe[y].insert(it);
}
maybe[x].clear();
}
void collapse(int x, int y) {
while (x != y) {
unite(x, y);
y = par[y];
}
int a = gtree(gcc(x)), b = gcc(x);
tree[b] = tree[a] = b;
}
void push(int v) {
v = gtree(gcc(v));
while (ac[v].size()) {
int t = ac[v].back(); ac[v].pop_back();
t = gcc(t);
if (v == t) continue;
int tv = gtree(v);
int tt = gtree(t);
if (tv != tt) {
add_edge(v, tt);
push(t);
return;
}
// cycle
collapse(v, t);
push(v);
return;
}
}
vi norm(int n, vi a) {
vi r(n);
for (int i : a) r[i] = 1;
return r;
}
vi find_reachable(vi r, vi u, vi v, vi c) {
int n = r.size();
int m = u.size();
vi ans;
for (int i = 0 ; i < n ; ++ i) {
tree[i] = cc[i] = par[i] = i;
}
for (int i = 0 ; i < m ; ++ i) {
maybe[u[i]].insert({c[i], v[i]});
maybe[v[i]].insert({c[i], u[i]});
}
for (int i = 0 ; i < n ; ++ i) {
keys[i].insert(r[i]);
auto it = maybe[i].lower_bound({r[i], -1});
while (it != maybe[i].end() && it->first == r[i]) ac[i].emplace_back(it->second), it++;
if (ac[i].empty()) ans.emplace_back(i);
}
if (ans.size()) return norm(n, ans);
for (int i = 0 ; i < n ; ++ i) {
push(i);
}
vi cnt(n);
for (int i = 0 ; i < n ; ++ i) {
int x = gcc(i);
if (x == gtree(x)) cnt[x]++;
else cnt[x] = N;
}
int mn = N;
for (int i = 0 ; i < n ; ++ i) {
int x = gcc(i);
mn = min(mn, cnt[x]);
}
for (int i = 0 ; i < n ; ++ i) {
int x = gcc(i);
if (cnt[x] == mn) ans.emplace_back(i);
}
return norm(n, ans);
}
컴파일 시 표준 에러 (stderr) 메시지
keys.cpp: In function 'void unite(int, int)':
keys.cpp:45:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
45 | for (auto i : del) maybe[y].erase(i); del.clear();
| ^~~
keys.cpp:45:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
45 | for (auto i : del) maybe[y].erase(i); del.clear();
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |