oj.uz

Submission #732822

# Submission time Handle Problem Language Result Execution time Memory
732822 2023-04-29T10:24:35 Z sentheta Duathlon (APIO18_duathlon) C++17
10 / 100
 1000 ms 28460 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 = 1e5+5;
const int M = 2e5+5;

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

int sz[N];
struct Dsu{
	int p[N];
	Dsu(){
		reset();
	}
	void reset(){
		rep(i,0,n+1) p[i]=i, sz[i]=1;
	}
	int find(int x){
		return p[x]==x ? x : p[x]=find(p[x]);
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	void unite(int x,int y){
		if((x=find(x))==(y=find(y))) return;
		p[y] = x;
		sz[x] += sz[y];
	}
} dsu;

bool bg[M];
int t[N], up[N], tim=0;
void dfs_bridge(int x=1,int par=-1){
	up[x] = t[x] = ++tim;

	for(int e : adj[x]){
		int y = edg[e].ff^edg[e].ss^x;
		if(y==par) continue;

		if(t[y]==-1){
			dfs_bridge(y, x);
		}
		up[x] = min(up[x],up[y]);

		if(up[y] > t[x]){
			bg[e] = 1;
			// cout << x _ y << nl;

			dsu.reset();
			rep(i,1,m+1) if(i!=e){
				dsu.unite(edg[i].ff, edg[i].ss);
			}
			assert(!dsu.same(x,y));
			// cout << x _ y << nl;
		}
		else{
			dsu.reset();
			rep(i,1,m+1) if(i!=e){
				dsu.unite(edg[i].ff, edg[i].ss);
			}
			assert(dsu.same(x,y));
			// cout << x _ y << nl;
		}
	}
}



V<int> cadj[N];
int ans = 0;

bool vis[N];
int tot;
void dfs_tot(int x,int par=-1){
	tot += sz[x];
	for(int y : cadj[x]) if(y!=par){
		dfs_tot(y, x);
	}
}
void dfs_dp(int x,int par=-1){
	vis[x] = 1;
	int orisz = sz[x];
	for(int y : cadj[x]) if(y!=par){
		dfs_dp(y, x);
		sz[x] += sz[y];
	}

	// dbg(x);
	// dbg(orisz); dbg(sz[x]);

	// S,C,T in this component
	ans += orisz *(orisz-1) *(orisz-2);
	// dbg(orisz *(orisz-1) *(orisz-2));

	// S,C in this component
	// C,T in this component
	ans += 2 *(orisz-1) *(orisz-1) *(tot-orisz);
	// dbg(2 *(orisz-1) *(orisz-1) *(tot-orisz));


	// C is LCA
	// C in this component, S from a child, T from other child
	for(int y : cadj[x]) if(y!=par){
		ans += orisz *sz[y] *(sz[x]-orisz-sz[y]);
		// dbg(orisz *sz[y] *(sz[x]-1-sz[y]));
	}

	// C is not LCA
	// C in this component, S from a child, T from parent
	// C in this component, T from a child, C from parent
	ans += 2 *orisz *(sz[x]-orisz) *(tot-sz[x]);
	// dbg(2 *orisz *(sz[x]-orisz) *(tot-sz[x]));

	// dbg(ans);
	// cout << nl;
}

void solve(){
	
	cin >> n >> m;
	
	rep(e,1,m+1){
		int u, v;
		cin >> u >> v;

		edg[e] = {u,v};
		adj[u].push_back(e);
		adj[v].push_back(e);
	}
	

	rep(i,1,n+1) t[i] = -1;
	rep(i,1,n+1) if(t[i]==-1){
		dfs_bridge(i);
	}

	dsu.reset();
	rep(e,1,m+1) if(!bg[e]){
		auto[x,y] = edg[e];
		// cout << "UNITE" _ x _ y << nl;
		dsu.unite(x,y);
	}
	rep(e,1,m+1) if(bg[e]){
		auto[x,y] = edg[e];
		x = dsu.find(x);
		y = dsu.find(y);

		cadj[x].push_back(y);
		cadj[y].push_back(x);
	}

	rep(i,1,n+1)
	// for(int i=n; i>=1; i--)
	if(i==dsu.find(i) && !vis[i]){
		// dbg(i);
		tot = 0;
		dfs_tot(dsu.find(i));
		// dbg(tot);
		dfs_dp(dsu.find(i));
		// dbg(ans);

		// cout << nl << nl;
	}

	cout << ans << nl;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1041 ms 28460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5076 KB Output is correct
2 Correct 14 ms 5144 KB Output is correct
3 Correct 13 ms 5076 KB Output is correct
4 Correct 12 ms 5252 KB Output is correct
5 Correct 11 ms 5184 KB Output is correct
6 Correct 12 ms 5204 KB Output is correct
7 Correct 11 ms 5204 KB Output is correct
8 Correct 11 ms 5188 KB Output is correct
9 Correct 11 ms 5204 KB Output is correct
10 Correct 13 ms 5076 KB Output is correct
11 Correct 13 ms 5144 KB Output is correct
12 Correct 12 ms 5144 KB Output is correct
13 Correct 13 ms 5140 KB Output is correct
14 Correct 11 ms 5096 KB Output is correct
15 Correct 11 ms 5132 KB Output is correct
16 Correct 5 ms 5076 KB Output is correct
17 Correct 12 ms 5152 KB Output is correct
18 Correct 12 ms 5076 KB Output is correct
19 Correct 13 ms 5264 KB Output is correct
20 Correct 15 ms 5160 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 13336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5076 KB Output is correct
2 Correct 14 ms 5076 KB Output is correct
3 Incorrect 19 ms 5148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 13320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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