#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
const int MXN = 100005;
int n, m;
struct DSU {
int p[MXN];
void init(int n) {
fill(p + 1, p + n + 1, -1);
}
int find(int x) {
return (p[x] < 0 ? x : p[x] = find(p[x]));
}
bool onion(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
p[y] += p[x];
p[x] = y;
return true;
}
};
namespace DS {
DSU dsu;
map<int, vector<int>> M[MXN];
int deg[MXN];
set<int> S[MXN];
queue<pii> q;
int ansE = 0, ansG = 0;
int tri(int x) {
return x * (x - 1);
}
int SIZE(int x) {
return -dsu.p[x];
}
void init(int n) {
dsu.init(n);
}
void SET_EDGE(int t, int x, int y) {
debug('+', t, y);
deg[y]++;
M[y][x].push_back(t);
S[t].insert(y);
ansE += SIZE(y);
}
void MERGE(int x, int y) {
ansG -= tri(SIZE(x));
ansG -= tri(SIZE(y));
for (auto &i : M[x][y]) {
ansE -= SIZE(x);
S[i].erase(x);
deg[x]--;
debug('-', i, x);
}
M[x].erase(y);
for (auto &i : M[y][x]) {
ansE -= SIZE(y);
S[i].erase(y);
deg[y]--;
debug('-', i, y);
}
M[y].erase(x);
if (deg[x] >= deg[y]) swap(x, y);
for (auto it = M[x].begin(); it != M[x].end(); it++) {
for (auto &i : it -> sc) {
ansE -= SIZE(x);
S[i].erase(x);
debug('-', i, x);
q.push(mp(i, y));
}
}
deg[x] = 0;
ansE -= deg[y] * SIZE(y);
M[x].clear();
dsu.onion(x, y);
ansE += deg[y] * SIZE(y);
ansG += tri(SIZE(y));
}
void ADD_EDGE(int t, int y) {
if (S[t].count(y)) return;
int x = dsu.find(t);
auto it = M[x].find(y);
if (it == M[x].end() || it -> sc.empty()) {
SET_EDGE(t, x, y);
return;
}
MERGE(x, y);
}
void clear_queue() {
while (q.size()) {
auto [x, y] = q.front();
q.pop();
y = dsu.find(y);
ADD_EDGE(x, y);
}
}
void COUT() {
cout << "dsu: ";
FOR(i, 1, n + 1) cout << dsu.find(i) << ' ';
cout << endl;
}
}
void miku() {
int a, b;
cin >> n >> m;
DS::init(n);
while (m--) {
cin >> a >> b;
DS::q.push(mp(a, b));
DS::clear_queue();
// DS::COUT();
cout << DS::ansE + DS::ansG << '\n';
}
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(iostream::failbit);
miku();
return 0;
}
Compilation message
joitter2.cpp: In function 'void DS::SET_EDGE(long long int, long long int, long long int)':
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
joitter2.cpp:62:9: note: in expansion of macro 'debug'
62 | debug('+', t, y);
| ^~~~~
joitter2.cpp: In function 'void DS::MERGE(long long int, long long int)':
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
joitter2.cpp:76:13: note: in expansion of macro 'debug'
76 | debug('-', i, x);
| ^~~~~
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
joitter2.cpp:83:13: note: in expansion of macro 'debug'
83 | debug('-', i, y);
| ^~~~~
joitter2.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) 39
| ^~
joitter2.cpp:91:17: note: in expansion of macro 'debug'
91 | debug('-', i, x);
| ^~~~~
joitter2.cpp: In function 'void DS::clear_queue()':
joitter2.cpp:116:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
116 | auto [x, y] = q.front();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
