oj.uz

답안 #911486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911486 2024-01-19T02:00:40 Z prairie2022 철인 이종 경기 (APIO18_duathlon) C++17
31 / 100
 87 ms 27220 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;

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);
	return cnt;
}


int 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--;
		tree_dp(i, 0);
	}
	cout << (ans<<1) << '\n';
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 25548 KB Output is correct
2 Correct 47 ms 25376 KB Output is correct
3 Correct 60 ms 23760 KB Output is correct
4 Correct 50 ms 23752 KB Output is correct
5 Correct 69 ms 21024 KB Output is correct
6 Correct 56 ms 22860 KB Output is correct
7 Correct 65 ms 20696 KB Output is correct
8 Correct 73 ms 21728 KB Output is correct
9 Correct 47 ms 19360 KB Output is correct
10 Correct 47 ms 19536 KB Output is correct
11 Correct 39 ms 17288 KB Output is correct
12 Correct 58 ms 16828 KB Output is correct
13 Correct 38 ms 16736 KB Output is correct
14 Correct 55 ms 16288 KB Output is correct
15 Correct 32 ms 15120 KB Output is correct
16 Correct 26 ms 14932 KB Output is correct
17 Correct 3 ms 8284 KB Output is correct
18 Correct 3 ms 8284 KB Output is correct
19 Correct 3 ms 8284 KB Output is correct
20 Correct 3 ms 8284 KB Output is correct
21 Correct 3 ms 8284 KB Output is correct
22 Correct 3 ms 8284 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 3 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8284 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 3 ms 8368 KB Output is correct
9 Correct 3 ms 8284 KB Output is correct
10 Correct 3 ms 8292 KB Output is correct
11 Correct 3 ms 8284 KB Output is correct
12 Correct 3 ms 8316 KB Output is correct
13 Correct 3 ms 8284 KB Output is correct
14 Correct 3 ms 8284 KB Output is correct
15 Correct 3 ms 8284 KB Output is correct
16 Correct 3 ms 8284 KB Output is correct
17 Correct 3 ms 8284 KB Output is correct
18 Correct 3 ms 8284 KB Output is correct
19 Correct 3 ms 8284 KB Output is correct
20 Correct 3 ms 8280 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 19080 KB Output is correct
2 Correct 54 ms 19140 KB Output is correct
3 Correct 62 ms 19080 KB Output is correct
4 Correct 57 ms 19020 KB Output is correct
5 Correct 54 ms 19120 KB Output is correct
6 Correct 60 ms 27220 KB Output is correct
7 Correct 65 ms 24568 KB Output is correct
8 Correct 60 ms 23124 KB Output is correct
9 Correct 87 ms 21952 KB Output is correct
10 Correct 54 ms 19024 KB Output is correct
11 Correct 57 ms 19028 KB Output is correct
12 Correct 53 ms 19132 KB Output is correct
13 Correct 75 ms 19028 KB Output is correct
14 Correct 56 ms 18260 KB Output is correct
15 Correct 41 ms 17752 KB Output is correct
16 Correct 28 ms 15160 KB Output is correct
17 Correct 41 ms 19668 KB Output is correct
18 Correct 40 ms 19540 KB Output is correct
19 Correct 44 ms 19584 KB Output is correct
20 Correct 39 ms 19540 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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