oj.uz

Submission #733204

# Submission time Handle Problem Language Result Execution time Memory
733204 2023-04-30T08:29:38 Z sentheta Duathlon (APIO18_duathlon) C++17
31 / 100
 125 ms 30984 KB 
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	srand(chrono::steady_clock::now().time_since_epoch().count());
	cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}








const int N = 2e5+5;

int n, m;
V<int> adj[N];

bool vis[N];

V<int> cadj[N], stak;
int id;

bool art[N];
int t[N], up[N], tim=0;
void dfs_art(int x,int par){
	up[x] = t[x] = ++tim;
	stak.push_back(x);
		
	int children = 0;
	for(int y : adj[x]) if(y!=par){
		if(!t[y]){
			children++;
			dfs_art(y, x);
		
			// new bcc
			if(up[y] >= t[x]){
				cadj[x].push_back(++id);
				cadj[id].push_back(x);
				// dbg(x); dbg(id); dbg(y);
				while(stak.back()!=x){
					cadj[stak.back()].push_back(id);
					cadj[id].push_back(stak.back());
					stak.pop_back();
				}
			}
		}

		up[x] = min(up[x], up[y]);
		if(par!=-1) art[x] = up[y]>=t[x];
	}
	if(par==-1) art[x] = children>=2;
}


int sz[N];
void dfs_sz(int x,int par){
	vis[x] = 1;
	for(int y : cadj[x]) if(y!=par){
		dfs_sz(y, x);
		sz[x] += sz[y];
	}
}

int ans = 0;
void reroot(int x,int par){
	vis[x] = 1;
	if(x > n){
		// dbg(x);
		int sum = 0;
		for(int y : cadj[x]){
			// dbg(y); dbg(sz[y]);
			sum += sz[y]*(sz[y]-1);
		}
		for(int y : cadj[x]){
			ans -= sum -sz[y]*(sz[y]-1);
		}
		// dbg(ans);
		// cout << nl;
	}

	int orisz = sz[x];
	for(int y : cadj[x]) if(y!=par){
		sz[x] = orisz - sz[y];
		sz[y] += sz[x];

		reroot(y, x);
	}
}

void solve(){
	
	cin >> n >> m;

	rep(i,0,m){
		int u, v; cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	id = n;
	rep(x,1,n+1) if(!t[x]){
		dfs_art(x, -1);
	}

	// cout << "ART[] ";
	// rep(x,1,n+1) if(art[x]) cout << x << " ";
	// cout << endl << endl;

	// cout << "BCC" << nl;
	// rep(x,1,n+1) for(int y : cadj[x]){
	// 	cout << x _ y << nl;
	// }
	// cout << endl;

	// return;

	rep(x,1,n+1){
		vis[x] = 0;
		sz[x] = 1;
	}
	rep(x,1,n+1) if(!vis[x]){
		dfs_sz(x, -1);
		ans += sz[x] *(sz[x]-1) *(sz[x]-2);
	}
	// dbg(ans);


	rep(x,1,id+1){
		vis[x] = 0;
	}
	rep(x,1,id+1) if(!vis[x]){
		reroot(x, -1);
	}

	cout << ans << nl;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 5 ms 9732 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 5 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 5 ms 9732 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 5 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 30744 KB Output is correct
2 Correct 81 ms 30672 KB Output is correct
3 Correct 79 ms 27708 KB Output is correct
4 Correct 73 ms 29160 KB Output is correct
5 Correct 79 ms 25208 KB Output is correct
6 Correct 97 ms 26672 KB Output is correct
7 Correct 100 ms 25024 KB Output is correct
8 Correct 84 ms 25436 KB Output is correct
9 Correct 84 ms 23868 KB Output is correct
10 Correct 80 ms 24064 KB Output is correct
11 Correct 80 ms 21908 KB Output is correct
12 Correct 67 ms 21628 KB Output is correct
13 Correct 67 ms 21556 KB Output is correct
14 Correct 76 ms 21296 KB Output is correct
15 Correct 51 ms 20232 KB Output is correct
16 Correct 56 ms 19880 KB Output is correct
17 Correct 11 ms 13180 KB Output is correct
18 Correct 10 ms 13140 KB Output is correct
19 Correct 10 ms 13128 KB Output is correct
20 Correct 9 ms 13184 KB Output is correct
21 Correct 9 ms 13136 KB Output is correct
22 Correct 10 ms 13136 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9864 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 6 ms 9868 KB Output is correct
4 Correct 6 ms 9940 KB Output is correct
5 Correct 8 ms 9916 KB Output is correct
6 Correct 6 ms 9816 KB Output is correct
7 Correct 7 ms 9892 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 6 ms 9892 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 7 ms 9812 KB Output is correct
12 Correct 7 ms 9860 KB Output is correct
13 Correct 6 ms 9812 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 5 ms 9856 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 6 ms 9864 KB Output is correct
19 Correct 6 ms 9884 KB Output is correct
20 Correct 5 ms 9812 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 24996 KB Output is correct
2 Correct 100 ms 24912 KB Output is correct
3 Correct 96 ms 24976 KB Output is correct
4 Correct 93 ms 24912 KB Output is correct
5 Correct 99 ms 24996 KB Output is correct
6 Correct 99 ms 30984 KB Output is correct
7 Correct 113 ms 29384 KB Output is correct
8 Correct 115 ms 28204 KB Output is correct
9 Correct 108 ms 27044 KB Output is correct
10 Correct 120 ms 24908 KB Output is correct
11 Correct 96 ms 24928 KB Output is correct
12 Correct 99 ms 25004 KB Output is correct
13 Correct 125 ms 24904 KB Output is correct
14 Correct 109 ms 24140 KB Output is correct
15 Correct 76 ms 23256 KB Output is correct
16 Correct 48 ms 20096 KB Output is correct
17 Correct 63 ms 25192 KB Output is correct
18 Correct 65 ms 25208 KB Output is correct
19 Correct 73 ms 25528 KB Output is correct
20 Correct 92 ms 25252 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9856 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Incorrect 6 ms 9860 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 24904 KB Output is correct
2 Correct 119 ms 24656 KB Output is correct
3 Incorrect 104 ms 24524 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 5 ms 9732 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 5 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9720 KB Output is correct
5 Correct 5 ms 9732 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 5 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -