#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t,n,q,par[N],cnt[N],sz[N], ans = 0;
map<int,int> follows[N], part[N];
vector<pair<int,pii> > edges[N];
int parent(int u) {
return par[u] == u ? u : par[u] = parent(par[u]);
}
void merge(int u,int v) {
u = parent(u), v = parent(v);
if(u == v) return;
if(edges[u].size() < edges[v].size()) swap(u,v);
ans -= cnt[u] * sz[u];
ans -= sz[v] * cnt[v];
cnt[u] += cnt[v];
int f = 0;
vector<int> x;
for(int i = 0; i < edges[v].size(); i++) {
int F = 0;
int type = edges[v][i].f, a = edges[v][i].s.s, b = edges[v][i].s.f;
if(type == 1) {
if(parent(a) == u || part[a][u]) F = 1,cnt[u]--;
if(follows[parent(u)][parent(a)]) F = 1, x.push_back(a);
follows[parent(a)][u] += follows[parent(a)][v];
part[a][u] = 1;
}
else {
if(parent(a) == u) {
F = 1;
if(!f) cnt[u]--,f = 1;
}
if(follows[parent(a)][u]) F = 1, x.push_back(a);
follows[u][parent(a)] += follows[v][parent(a)];
part[b][parent(a)] = 1;
}
if(!F) edges[u].push_back(edges[v][i]);
}
ans += sz[u] * sz[v] * 2 + cnt[u] * (sz[u] + sz[v]);
par[v] = u;
sz[u] += sz[v];
for(int i = 0; i < x.size(); i++) merge(u,x[i]);
}
main(){
cin >> n >> q;
for(int i = 1; i <= n; i++) {
par[i] = i;
sz[i] = 1;
}
while(q--) {
int u,v;
cin >> u >> v;
if(parent(u) == parent(v) || part[u][parent(v)]) {
cout << ans <<"\n";
continue;
}
if(follows[parent(v)][parent(u)]) {
merge(u,v);
}
else if(!part[u][parent(v)]){
follows[parent(u)][parent(v)] = 1;
part[u][parent(v)] = 1;
edges[parent(u)].push_back({0,{u,v}});
edges[parent(v)].push_back({1,{v,u}});
ans += sz[parent(v)];
cnt[parent(v)]++;
}
cout << ans << "\n";
}
}
Compilation message
joitter2.cpp: In function 'void merge(long long int, long long int)':
joitter2.cpp:23:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i = 0; i < edges[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
joitter2.cpp:46:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0; i < x.size(); i++) merge(u,x[i]);
| ~~^~~~~~~~~~
joitter2.cpp: At global scope:
joitter2.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
49 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23800 KB |
Output is correct |
| 3 |
Correct |
14 ms |
23800 KB |
Output is correct |
| 4 |
Correct |
14 ms |
23760 KB |
Output is correct |
| 5 |
Correct |
14 ms |
23708 KB |
Output is correct |
| 6 |
Correct |
14 ms |
23724 KB |
Output is correct |
| 7 |
Incorrect |
19 ms |
23756 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23800 KB |
Output is correct |
| 3 |
Correct |
14 ms |
23800 KB |
Output is correct |
| 4 |
Correct |
14 ms |
23760 KB |
Output is correct |
| 5 |
Correct |
14 ms |
23708 KB |
Output is correct |
| 6 |
Correct |
14 ms |
23724 KB |
Output is correct |
| 7 |
Incorrect |
19 ms |
23756 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23756 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23800 KB |
Output is correct |
| 3 |
Correct |
14 ms |
23800 KB |
Output is correct |
| 4 |
Correct |
14 ms |
23760 KB |
Output is correct |
| 5 |
Correct |
14 ms |
23708 KB |
Output is correct |
| 6 |
Correct |
14 ms |
23724 KB |
Output is correct |
| 7 |
Incorrect |
19 ms |
23756 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
