Submission #911486

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
911486	2024-01-19T02:00:40 Z	prairie2022	Duathlon (APIO18_duathlon)	C++17	31 / 100	87 ms	27220 KB

count_triplets

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-

Submission #911486

Compilation message