#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
ll ans = 0;
ll sq = 500;
ll n, m;
ll prt[100009];
ll sz[100009];
ll bigid[100009];
ll curbig = 1;
int bigin[509][100009];
int bigout[509][100009];
ll totin[100009];
vector<ll> in[100009];
vector<ll> out[100009];
bitset<100009> tmp;
vector<ll> normal[100009];
ll findprt(ll x){
if(prt[x] == x) return x;
return prt[x] = findprt(prt[x]);
}
void makebig(ll x){
bigid[x] = curbig++;
for(auto u : in[x]){
bigin[bigid[x]][findprt(u)]++;
if(findprt(u) != x)
totin[x]++;
}
for(auto u : out[x])
bigout[bigid[x]][findprt(u)]++;
}
ll calc(ll x){
if(bigid[x]) return totin[x]*sz[x];
ll cur = 0;
for(auto u : in[x])
if(findprt(u) != x) cur += sz[x];
return cur;
}
void merge(ll x, ll y){
x = findprt(x);
y = findprt(y);
if(x == y) return;
if(bigid[y] || (!bigid[x] && in[y].size()+out[y].size() > in[x].size()+out[x].size()))
swap(x, y);
if(bigid[x]){
if(bigin[bigid[x]][y] == 0 || bigout[bigid[x]][y] == 0)
return;
}
else{
ll goin = 0;
ll goout = 0;
for(auto u : in[y])
if(findprt(u) == x)++goin;
for(auto u : out[y])
if(findprt(u) == x)++goout;
if(goin == 0 || goout == 0)
return;
}
ans -= calc(x)+calc(y);
vector<ll> mergelater;
if(bigid[x] && bigid[y]){
totin[x] -= bigin[bigid[x]][y];
prt[y] = x;
for(int i = 1; i <= n; ++i){
if(findprt(i) != i || i == x) continue;
totin[x] += bigin[bigid[y]][i];
bigout[bigid[x]][i] += bigout[bigid[y]][i];
bigin[bigid[x]][i] += bigin[bigid[y]][i];
if(bigout[bigid[x]][i] && bigin[bigid[x]][i])
mergelater.pb(i);
}
ans -= sz[x]*(sz[x]-1)+sz[y]*(sz[y]-1);
sz[x] += sz[y];
ans += sz[x]*(sz[x]-1);
}
else if(bigid[x]){
totin[x] -= bigin[bigid[x]][y];
prt[y] = x;
for(auto u : in[y]){
bigin[bigid[x]][findprt(u)]++;
if(findprt(u) != x)
totin[x]++;
if(findprt(u) != x && bigout[bigid[x]][u])
mergelater.pb(u);
}
for(auto u : out[y]){
bigout[bigid[x]][findprt(u)]++;
if(findprt(u) != x && bigin[bigid[x]][u])
mergelater.pb(u);
}
ans -= sz[x]*(sz[x]-1)+sz[y]*(sz[y]-1);
sz[x] += sz[y];
ans += sz[x]*(sz[x]-1);
}
else{
prt[y] = x;
for(auto u : in[y])
if(findprt(u) != x) in[x].pb(u);
for(auto u : out[y])
if(findprt(u) != x) out[x].pb(u);
ans -= sz[x]*(sz[x]-1)+sz[y]*(sz[y]-1);
sz[x] += sz[y];
ans += sz[x]*(sz[x]-1);
for(auto u : in[x])
tmp[findprt(u)] = 1;
for(auto u : out[x])
if(tmp[findprt(u)] && findprt(u) != x)
mergelater.pb(u);
for(auto u : in[x])
tmp[findprt(u)] = 0;
}
for(ll i = 1; i < curbig; ++i){
bigin[i][x] += bigin[i][y];
bigin[i][y] = 0;
bigout[i][x] += bigout[i][y];
bigout[i][y] = 0;
}
if(!bigid[x] && in[x].size()+out[x].size() > sq)
makebig(x);
ans += calc(x);
for(auto u : mergelater)
merge(x, u);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> m;
for(ll i = 1; i <= n; ++i){
sz[i] = 1;
prt[i] = i;
}
while(m--){
ll x, y;
cin >> x >> y;
ll dont = 0;
for(auto u : normal[x])
if(findprt(u) == findprt(y))
dont = 1;
if(dont){
cout << ans << '\n';
continue;
}
normal[x].pb(y);
x = findprt(x);
y = findprt(y);
if(x != y) ans += sz[y];
if(bigid[x])
bigout[bigid[x]][y]++;
else
out[x].pb(y);
if(bigid[y]){
bigin[bigid[y]][x]++;
totin[y]++;
}
else
in[y].pb(x);
merge(x, y);
cout << ans << '\n';
}
}
Compilation message
joitter2.cpp: In function 'void merge(ll, ll)':
joitter2.cpp:129:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(!bigid[x] && in[x].size()+out[x].size() > sq)
~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
