이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/extc++.h>
template <class T> using Vec = std::vector<T>;
template <class T, class U> using Map = std::unordered_map<T, U>;
int scan() {
int x;
std::scanf("%d", &x);
return x;
}
void print(const long long x) {
std::printf("%lld\n", x);
}
struct DSU {
Vec<int> par;
DSU(const int n) : par(n, -1) {}
int find(const int x) {
return par[x] < 0 ? x : par[x] = find(par[x]);
}
int size(const int x) {
return -par[find(x)];
}
void absorb(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
par[x] += par[y];
par[y] = x;
}
}
};
int main() {
const int N = scan();
int M = scan();
Vec<Map<int, std::set<int>>> in(N), out(N);
Vec<int> sum(N);
DSU dsu(N);
long long answer = 0;
std::queue<std::pair<int, int>> merge;
const auto remove = [&](const int x, const int y) {
const int s = out[y][x].size();
const int t = out[x][y].size();
answer -= (long long) dsu.size(x) * s;
answer -= (long long) dsu.size(y) * t;
sum[x] -= s + t;
sum[y] -= s + t;
in[x].erase(y);
out[x].erase(y);
in[y].erase(x);
out[y].erase(x);
};
const auto process = [&] {
while (!merge.empty()) {
auto [x, y] = merge.front();
merge.pop();
x = dsu.find(x);
y = dsu.find(y);
if (x == y) {
continue;
}
remove(x, y);
if (sum[y] > sum[x]) {
std::swap(x, y);
}
answer += (long long) dsu.size(x) * dsu.size(y) * 2;
for (auto &[z, set] : in[y]) {
assert(!set.empty());
answer -= (long long) set.size() * dsu.size(y);
if (out[x].find(z) != out[x].end()) {
merge.emplace(x, z);
}
for (const auto u : set) {
if (in[x][z].insert(u).second) {
sum[x] += 1;
sum[z] += 1;
answer += dsu.size(x);
out[z][x].insert(u);
}
}
sum[z] -= out[z][y].size();
out[z].erase(y);
}
for (const auto &[z, set] : in[x]) {
answer += (long long) dsu.size(y) * set.size();
}
for (auto &[z, set] : out[y]) {
assert(!set.empty());
if (out[z].find(x) != out[z].end()) {
merge.emplace(x, z);
}
for (const auto u : set) {
sum[x] += 1;
sum[z] += 1;
out[x][z].insert(u);
in[z][x].insert(u);
}
sum[z] -= in[z][y].size();
in[z].erase(y);
}
in[y].clear();
out[y].clear();
sum[y] = 0;
dsu.absorb(x, y);
}
};
while (M--) {
const int a = scan() - 1;
const int b = scan() - 1;
const int u = dsu.find(a);
const int v = dsu.find(b);
if (u != v) {
if (in[u].find(v) != in[u].end()) {
merge.emplace(u, v);
process();
} else {
if (out[u][v].insert(a).second) {
sum[u] += 1;
sum[v] += 1;
in[v][u].insert(a);
answer += dsu.size(v);
}
}
}
print(answer);
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
joitter2.cpp: In function 'int scan()':
joitter2.cpp:8:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | std::scanf("%d", &x);
| ~~~~~~~~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |