oj.uz

답안 #911754

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911754 2024-01-19T05:06:25 Z prairie2022 철인 이종 경기 (APIO18_duathlon) C++17
31 / 100
 104 ms 25440 KB 
#include<bits/stdc++.h>
using namespace std;

#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
typedef long long ll;

#define int long long

const int M = 1e5+1;
vector<int> e[M];
int dfn[M], dfc;
int stk[M], top = -1, num;
vector<int> bct[M<<1];

int tarjan(int u){ // return low
	dfn[u] = ++dfc;
	stk[++top] = u;
	int low = dfn[u];
	for(const int &v: e[u]){
		if(dfn[v]) low = min(low, dfn[v]);
		else{
			int tmp = tarjan(v);
			if(tmp==dfn[u]){
				bct[++num].push_back(u);
				while(stk[top]!=u) bct[num].push_back(stk[top--]);
				for(const int &w: bct[num]) bct[w].push_back(num);
			}
			else low = min(low, tmp);
		}
	}
	return low;
}

int n;
ll ans = 0;

int tree_dp(int u, int p){
	ll sum = 0, cnt = (u<=n);
	for(const int &v : bct[u]){
		if(v==p) continue;
		int tmp = tree_dp(v, u);
		sum += cnt*tmp;
		cnt += tmp;
	}
	sum += cnt*(dfc-cnt);
	ans += sum*(u>n?(int)bct[u].size():-1);
	//cout << u << ' ' << sum << '\n';
	return cnt;
}

signed main(){
	fastio
	int m;
	cin >> n >> m;
	fill(dfn+1, dfn+n+1, 0);
	num = n;
	for(; m; m--){
		int u, v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1; i<=n; i++) if(!dfn[i] && !e[i].empty()){
		dfc = 0, tarjan(i), top--;
		/*for(int i=1; i<=num; i++){
			cout << i << " :";
			for(const int &v: bct[i]) cout << ' ' << v;
			cout << '\n';
		}*/
		tree_dp(i, 0);
	}
	cout << (ans<<1) << '\n';
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 25288 KB Output is correct
2 Correct 67 ms 25440 KB Output is correct
3 Correct 60 ms 22392 KB Output is correct
4 Correct 64 ms 23776 KB Output is correct
5 Correct 70 ms 20044 KB Output is correct
6 Correct 84 ms 21564 KB Output is correct
7 Correct 49 ms 19864 KB Output is correct
8 Correct 76 ms 20140 KB Output is correct
9 Correct 53 ms 18712 KB Output is correct
10 Correct 61 ms 18952 KB Output is correct
11 Correct 47 ms 17076 KB Output is correct
12 Correct 36 ms 16724 KB Output is correct
13 Correct 57 ms 16752 KB Output is correct
14 Correct 33 ms 16480 KB Output is correct
15 Correct 29 ms 15444 KB Output is correct
16 Correct 43 ms 15184 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 3 ms 9048 KB Output is correct
19 Correct 3 ms 9048 KB Output is correct
20 Correct 3 ms 9052 KB Output is correct
21 Correct 2 ms 9052 KB Output is correct
22 Correct 3 ms 9052 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 3 ms 9048 KB Output is correct
4 Correct 4 ms 9052 KB Output is correct
5 Correct 5 ms 9052 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 4 ms 9052 KB Output is correct
9 Correct 3 ms 9048 KB Output is correct
10 Correct 3 ms 9196 KB Output is correct
11 Correct 3 ms 9052 KB Output is correct
12 Correct 3 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 2 ms 9052 KB Output is correct
15 Correct 2 ms 9112 KB Output is correct
16 Correct 3 ms 9036 KB Output is correct
17 Correct 2 ms 9052 KB Output is correct
18 Correct 3 ms 9052 KB Output is correct
19 Correct 3 ms 9196 KB Output is correct
20 Correct 2 ms 9052 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 19540 KB Output is correct
2 Correct 64 ms 19580 KB Output is correct
3 Correct 55 ms 19536 KB Output is correct
4 Correct 55 ms 19536 KB Output is correct
5 Correct 60 ms 19536 KB Output is correct
6 Correct 74 ms 25168 KB Output is correct
7 Correct 92 ms 23636 KB Output is correct
8 Correct 92 ms 22432 KB Output is correct
9 Correct 83 ms 21564 KB Output is correct
10 Correct 104 ms 19520 KB Output is correct
11 Correct 69 ms 19540 KB Output is correct
12 Correct 57 ms 19592 KB Output is correct
13 Correct 69 ms 19524 KB Output is correct
14 Correct 52 ms 19136 KB Output is correct
15 Correct 41 ms 18004 KB Output is correct
16 Correct 35 ms 15452 KB Output is correct
17 Correct 40 ms 19912 KB Output is correct
18 Correct 58 ms 19780 KB Output is correct
19 Correct 46 ms 20152 KB Output is correct
20 Correct 51 ms 19928 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 19660 KB Output is correct
2 Correct 57 ms 19284 KB Output is correct
3 Incorrect 70 ms 19208 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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