oj.uz

답안 #732821

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
732821 2023-04-29T10:23:29 Z sentheta 철인 이종 경기 (APIO18_duathlon) C++17
10 / 100
 1000 ms 30068 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;
		}
	}
}



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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5052 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5052 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 30068 KB Output is correct
2 Correct 77 ms 29988 KB Output is correct
3 Execution timed out 1076 ms 21540 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 5148 KB Output is correct
2 Correct 14 ms 5076 KB Output is correct
3 Correct 15 ms 5076 KB Output is correct
4 Correct 12 ms 5316 KB Output is correct
5 Correct 12 ms 5196 KB Output is correct
6 Correct 12 ms 5212 KB Output is correct
7 Correct 11 ms 5256 KB Output is correct
8 Correct 12 ms 5204 KB Output is correct
9 Correct 11 ms 5180 KB Output is correct
10 Correct 13 ms 5204 KB Output is correct
11 Correct 15 ms 5196 KB Output is correct
12 Correct 13 ms 5160 KB Output is correct
13 Correct 13 ms 5076 KB Output is correct
14 Correct 12 ms 5184 KB Output is correct
15 Correct 9 ms 5076 KB Output is correct
16 Correct 5 ms 5076 KB Output is correct
17 Correct 13 ms 5076 KB Output is correct
18 Correct 13 ms 5160 KB Output is correct
19 Correct 13 ms 5204 KB Output is correct
20 Correct 13 ms 5204 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1073 ms 13416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 5076 KB Output is correct
2 Correct 14 ms 5144 KB Output is correct
3 Incorrect 11 ms 5160 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1086 ms 13268 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5052 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5052 KB Output is correct
7 Incorrect 3 ms 4948 KB Output isn't correct
8 Halted 0 ms 0 KB -