#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
#ifndef ONLINE_JUDGE
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
freopen("inp.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#else
#define er(args ...) 0
#endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 4e5 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}
struct DSU{
int par[maxn], cnt[maxn];
bool f = false;
DSU(bool f): f(f){
fill(par, par + maxn, -1);
fill(cnt, cnt + maxn, 1);
}
int get(int x){
return par[x] == -1? x: (f? par[x] = get(par[x]): get(par[x]));
}
vector<pp> his;
void unite(int u, int v){
u = get(u), v = get(v);
if(u - v){
if(cnt[u] < cnt[v]) swap(u, v);
par[v] = u, cnt[u] += v;
his.pb({u, v});
} else his.pb({-1, -1});
}
void undo(){
auto[u, v] = his.back(); his.pop_back();
if(u + 1){
par[v] = -1, cnt[u] -= cnt[v];
}
}
} node(false), edge(true);
vector<pp> adj[maxn];
vector<int> str[maxn];
bool vis[maxn], act[maxn];
void dvd(int l, int r){
if(l + 1 == r){
vector<int> tmp;
for(auto[c, e]: adj[l]){
int x = node.get(c);
tmp.pb(x);
str[x].pb(e);
}
for(int x: tmp) if(!vis[x]){
vis[x] = true;
rep(i,1,sz(str[x])){
edge.unite(str[x][i-1], str[x][i]);
}
str[x].clear();
}
for(int x: tmp) vis[x] = false;
return;
}
int mid = (l + r)>>1;
int cnt = 0;
rep(i,mid,r){
for(auto[c, e]: adj[i]){
if(act[c]){
node.unite(i, c);
cnt++;
}
}
act[i] = true;
}
dvd(l, mid);
while(cnt--) node.undo();
cnt = 0;
rep(i,mid,r) act[i] = false;
rep(i,l,mid){
for(auto[c, e]: adj[i]){
if(act[c]){
node.unite(i, c);
cnt++;
}
}
act[i] = true;
}
dvd(mid, r);
while(cnt--) node.undo();
rep(i,l,mid) act[i] = false;
}
vector<int> adj2[maxn];
int m, cnt[maxn], val[maxn];
ll ans = 0;
void dfs(int r, int p){
vis[r] = true;
cnt[r] = r >= m;
for(int c: adj2[r]) if(c - p){
dfs(c, r);
cnt[r] += cnt[c];
}
}
void dfs2(int r, int p, int tot){
if(r >= m){
for(int c: adj2[r]) if(c - p){
ans -= 1ll*(tot - cnt[c])*(tot - cnt[c] - 1)*(val[c] - 1);
}
if(p + 1){
ans -= 1ll*(cnt[r])*(cnt[r]-1)*(val[p] - 1);
}
}
for(int c: adj2[r]) if(c - p){
dfs2(c, r, tot);
}
}
int main(){ IOS();
int n; cin >> n >> m;
rep(i,0,m){
int u, v; cin >> u >> v; u--, v--;
adj[u].pb({v, i}), adj[v].pb({u, i});
}
dvd(0, n);
rep(r,0,n){
vector<int> tmp;
for(auto[c, e]: adj[r]){
int x = edge.get(e);
if(!vis[x]){
val[x]++;
vis[x] = true;
tmp.pb(x);
adj2[x].pb(r + m);
adj2[r + m].pb(x);
}
}
for(int x: tmp) vis[x] = false;
}
rep(i,m,n+m){
if(!vis[i]){
dfs(i, -1);
ans += 1ll*cnt[i]*(cnt[i]-1)*(cnt[i]-2);
dfs2(i, -1, cnt[i]);
}
}
cout << ans << '\n';
return 0-0;
}
Compilation message
count_triplets.cpp: In function 'void IOS()':
count_triplets.cpp:19:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen("inp.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:20:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
410 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
410 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
408 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
420 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
374 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
428 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
402 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
410 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
410 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
