#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e6 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
int n, m;
set<ii> edges;
set<int> to[N];// to includes all nodes that are inside to
int rt[N], sz[N];
int answer;
int root(int x){
return (x == rt[x] ? x : rt[x] = root(rt[x]));
}
void merge(int x, int y){
x = root(x), y = root(y);
if(x == y) return;
if(sz[x] < sz[y]) swap(x, y);
answer -= sz[x] * (to[x].size() - sz[x]);
answer -= (sz[x] * (sz[x] - 1));
answer -= sz[y] * (to[y].size() - sz[y]);
answer -= (sz[y] * (sz[y] - 1));
rt[y] = x;
sz[x] += sz[y];
for(auto it : to[y]) to[x].insert(it);
to[y].clear();
answer += sz[x] * (to[x].size() - sz[x]);
answer += sz[x] * (sz[x] - 1);
}
#ifdef local
void process(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
rt[i] = i, sz[i] = 1, to[i].insert(i);
}
for(int i = 1; i <= m; i++){
int x, y, yy;
cin >> x >> y;
yy = y;
y = root(y);
if(to[y].find(x) == to[y].end()){
to[y].insert(x);
answer += sz[y];
}
if(edges.find({yy, x}) != edges.end()) merge(x, yy);
edges.insert({x, yy});
cout << answer << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
47228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
47228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
47228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
