oj.uz

답안 #739118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
739118 2023-05-10T02:34:04 Z 089487 철인 이종 경기 (APIO18_duathlon) C++14
0 / 100
 153 ms 42452 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
const int N=2e5+7;
const int INF=1e18;
vector<int> v[N];
vector<int> v2[N];
vector<int> v3[N];
int in[N];
int low[N];
int t=1;
int num;
int sz[N];
bool cut[N];
stack<int> st;
void add_edge(int a,int b){
	v2[a].eb(b);
	v2[b].eb(a);
	//debug(a,"<->",b);
}
void dfs(int x,int p=-1){
	in[x]=low[x]=t++;
	st.push(x);
	bool ct=false;
	for(int i:v[x]){
		if(i==p) continue;
		if(in[i]) low[x]=min(low[x],in[i]);
		else{
			dfs(i,x);
			if(in[x]<=low[i]) ct=true;
			low[x]=min(low[x],low[i]);
		}
	}
	if(p==-1){
		ct=(sz(v[x])>=2);
	}
	if(p==-1||in[p]<=low[x]){
		++num;
		while(sz(st)){
			int x2=st.top();
			st.pop();
			add_edge(num,x2);
			if(x2==x) break;
		}
		if(p!=-1)add_edge(num,p);
		cut[num]=ct;
	}
}
pii e[N];
int sum;
int n;
int Sz[N];
int Sz2[N];
bool vis[N];
int fa[N];
int dep[N];
void dfs_sz(int x,int p=-1,int d=0){
	dep[x]=d;
	Sz[x]=sz[x];
	for(int i:v2[x]){
		if(i!=p){
			dfs_sz(i,x,d+1);
			Sz[x]+=Sz[i];
		}
	}
	sum=Sz[x];
}
int C2(int x){
	if(x<2) return 0;
	return x*(x-1);
}
int C3(int x){
	if(x<3) return 0;
	return x*(x-1)*(x-2);
}
int ans=0;
void solve(int x,int p=-1){
	fa[x]=p;
	vis[x]=true;
	for(int i:v2[x]){
		if(!vis[i]) solve(i,x);
	}
	if(x<=n){
		int s=0;

		// 1
		for(int i:v2[x]){
			int S2;
						
			if(i==p){
				S2=sum-Sz[x];
			}
			else{
				S2=Sz[i];	
			}
			ans+=s*S2*2;
			s+=S2;
			ans+=C2(S2);
		}
		/*for(int i:v2[x]){
			for(int j:v2[i]){
				if(j==x) continue;
				int S2;
				if(dep[j]<dep[i]){
					S2=sum-Sz[j];
				}
				else{

				}
			}
		}*/
	}
	else{
		int l=sz(v2[x]);
		for(int i:v2[x]){
			int S2;
			if(i==p){
				S2=sum-Sz[x];
			}
			else{
				S2=Sz[i];
			}
			ans-=(l-1)*C2(S2);
		}	
	}
}
signed main(){
	quick
	int m;
	cin>>n>>m;
	rep(i,1,m){
		cin>>e[i].F>>e[i].S;
		v[e[i].F].eb(e[i].S);
		v[e[i].S].eb(e[i].F);
	}
	num=n;
	dfs(1);
	rep(i,1,n) sz[i]=1;
	ans=0;
	rep(i,1,num){
		if(!vis[i]){
			dfs_sz(i);
			solve(i);
		}
	}
	//rep(i,1,n) cout<<Sz[i]<<" \n"[i==n];
	cout<<ans<<"\n";
	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 9 ms 14468 KB Output is correct
3 Correct 9 ms 14420 KB Output is correct
4 Correct 10 ms 14424 KB Output is correct
5 Correct 10 ms 14428 KB Output is correct
6 Correct 9 ms 14428 KB Output is correct
7 Correct 9 ms 14372 KB Output is correct
8 Correct 11 ms 14456 KB Output is correct
9 Correct 10 ms 14432 KB Output is correct
10 Correct 11 ms 14480 KB Output is correct
11 Correct 9 ms 14404 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 9 ms 14484 KB Output is correct
14 Correct 10 ms 14384 KB Output is correct
15 Correct 10 ms 14424 KB Output is correct
16 Correct 12 ms 14432 KB Output is correct
17 Correct 9 ms 14428 KB Output is correct
18 Correct 10 ms 14428 KB Output is correct
19 Incorrect 9 ms 14476 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 9 ms 14468 KB Output is correct
3 Correct 9 ms 14420 KB Output is correct
4 Correct 10 ms 14424 KB Output is correct
5 Correct 10 ms 14428 KB Output is correct
6 Correct 9 ms 14428 KB Output is correct
7 Correct 9 ms 14372 KB Output is correct
8 Correct 11 ms 14456 KB Output is correct
9 Correct 10 ms 14432 KB Output is correct
10 Correct 11 ms 14480 KB Output is correct
11 Correct 9 ms 14404 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 9 ms 14484 KB Output is correct
14 Correct 10 ms 14384 KB Output is correct
15 Correct 10 ms 14424 KB Output is correct
16 Correct 12 ms 14432 KB Output is correct
17 Correct 9 ms 14428 KB Output is correct
18 Correct 10 ms 14428 KB Output is correct
19 Incorrect 9 ms 14476 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 41632 KB Output is correct
2 Correct 89 ms 41684 KB Output is correct
3 Incorrect 67 ms 33316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14680 KB Output is correct
2 Correct 9 ms 14676 KB Output is correct
3 Correct 9 ms 14676 KB Output is correct
4 Correct 9 ms 14696 KB Output is correct
5 Correct 12 ms 14676 KB Output is correct
6 Correct 9 ms 14676 KB Output is correct
7 Correct 11 ms 14688 KB Output is correct
8 Correct 8 ms 14676 KB Output is correct
9 Correct 9 ms 14676 KB Output is correct
10 Incorrect 9 ms 14524 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 35088 KB Output is correct
2 Correct 105 ms 35208 KB Output is correct
3 Correct 129 ms 35180 KB Output is correct
4 Correct 127 ms 35276 KB Output is correct
5 Correct 124 ms 35104 KB Output is correct
6 Correct 111 ms 42452 KB Output is correct
7 Correct 126 ms 40368 KB Output is correct
8 Correct 153 ms 38936 KB Output is correct
9 Correct 142 ms 37740 KB Output is correct
10 Incorrect 92 ms 31104 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14676 KB Output is correct
2 Correct 9 ms 14612 KB Output is correct
3 Correct 10 ms 14616 KB Output is correct
4 Correct 10 ms 14660 KB Output is correct
5 Correct 9 ms 14528 KB Output is correct
6 Correct 10 ms 14564 KB Output is correct
7 Correct 10 ms 14548 KB Output is correct
8 Correct 9 ms 14596 KB Output is correct
9 Correct 10 ms 14536 KB Output is correct
10 Correct 10 ms 14548 KB Output is correct
11 Correct 9 ms 14560 KB Output is correct
12 Correct 9 ms 14740 KB Output is correct
13 Correct 9 ms 14652 KB Output is correct
14 Correct 9 ms 14684 KB Output is correct
15 Correct 9 ms 14676 KB Output is correct
16 Incorrect 9 ms 14564 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 35200 KB Output is correct
2 Correct 124 ms 34916 KB Output is correct
3 Correct 127 ms 34816 KB Output is correct
4 Correct 110 ms 33684 KB Output is correct
5 Correct 111 ms 31928 KB Output is correct
6 Correct 106 ms 31168 KB Output is correct
7 Correct 128 ms 30948 KB Output is correct
8 Correct 113 ms 30340 KB Output is correct
9 Correct 93 ms 30216 KB Output is correct
10 Correct 78 ms 30048 KB Output is correct
11 Correct 86 ms 29772 KB Output is correct
12 Correct 85 ms 29784 KB Output is correct
13 Correct 93 ms 29908 KB Output is correct
14 Correct 80 ms 32496 KB Output is correct
15 Correct 134 ms 40504 KB Output is correct
16 Correct 129 ms 38692 KB Output is correct
17 Correct 130 ms 38952 KB Output is correct
18 Correct 140 ms 37348 KB Output is correct
19 Incorrect 106 ms 33208 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 9 ms 14468 KB Output is correct
3 Correct 9 ms 14420 KB Output is correct
4 Correct 10 ms 14424 KB Output is correct
5 Correct 10 ms 14428 KB Output is correct
6 Correct 9 ms 14428 KB Output is correct
7 Correct 9 ms 14372 KB Output is correct
8 Correct 11 ms 14456 KB Output is correct
9 Correct 10 ms 14432 KB Output is correct
10 Correct 11 ms 14480 KB Output is correct
11 Correct 9 ms 14404 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 9 ms 14484 KB Output is correct
14 Correct 10 ms 14384 KB Output is correct
15 Correct 10 ms 14424 KB Output is correct
16 Correct 12 ms 14432 KB Output is correct
17 Correct 9 ms 14428 KB Output is correct
18 Correct 10 ms 14428 KB Output is correct
19 Incorrect 9 ms 14476 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 9 ms 14468 KB Output is correct
3 Correct 9 ms 14420 KB Output is correct
4 Correct 10 ms 14424 KB Output is correct
5 Correct 10 ms 14428 KB Output is correct
6 Correct 9 ms 14428 KB Output is correct
7 Correct 9 ms 14372 KB Output is correct
8 Correct 11 ms 14456 KB Output is correct
9 Correct 10 ms 14432 KB Output is correct
10 Correct 11 ms 14480 KB Output is correct
11 Correct 9 ms 14404 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 9 ms 14484 KB Output is correct
14 Correct 10 ms 14384 KB Output is correct
15 Correct 10 ms 14424 KB Output is correct
16 Correct 12 ms 14432 KB Output is correct
17 Correct 9 ms 14428 KB Output is correct
18 Correct 10 ms 14428 KB Output is correct
19 Incorrect 9 ms 14476 KB Output isn't correct
20 Halted 0 ms 0 KB -