Submission #911540

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
911540	2024-01-19T03:24:22 Z	prairie2022	Duathlon (APIO18_duathlon)	C++17	31 / 100	100 ms	27084 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);
	//cout << u << ' ' << sum << '\n';
	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--;
		/*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

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8280 KB	Output is correct
2	Correct	2 ms	8284 KB	Output is correct
3	Correct	3 ms	8028 KB	Output is correct
4	Correct	3 ms	8284 KB	Output is correct
5	Correct	3 ms	8040 KB	Output is correct
6	Correct	2 ms	8028 KB	Output is correct
7	Incorrect	3 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	8280 KB	Output is correct
2	Correct	2 ms	8284 KB	Output is correct
3	Correct	3 ms	8028 KB	Output is correct
4	Correct	3 ms	8284 KB	Output is correct
5	Correct	3 ms	8040 KB	Output is correct
6	Correct	2 ms	8028 KB	Output is correct
7	Incorrect	3 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	53 ms	24972 KB	Output is correct
2	Correct	54 ms	24996 KB	Output is correct
3	Correct	71 ms	23276 KB	Output is correct
4	Correct	52 ms	23204 KB	Output is correct
5	Correct	51 ms	20560 KB	Output is correct
6	Correct	71 ms	22224 KB	Output is correct
7	Correct	100 ms	20300 KB	Output is correct
8	Correct	56 ms	20820 KB	Output is correct
9	Correct	56 ms	18772 KB	Output is correct
10	Correct	74 ms	19092 KB	Output is correct
11	Correct	40 ms	16728 KB	Output is correct
12	Correct	46 ms	16464 KB	Output is correct
13	Correct	52 ms	16464 KB	Output is correct
14	Correct	45 ms	16208 KB	Output is correct
15	Correct	44 ms	14928 KB	Output is correct
16	Correct	38 ms	14684 KB	Output is correct
17	Correct	3 ms	8280 KB	Output is correct
18	Correct	2 ms	8284 KB	Output is correct
19	Correct	3 ms	8284 KB	Output is correct
20	Correct	3 ms	8280 KB	Output is correct
21	Correct	3 ms	8280 KB	Output is correct
22	Correct	4 ms	8284 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8280 KB	Output is correct
2	Correct	3 ms	8284 KB	Output is correct
3	Correct	3 ms	8384 KB	Output is correct
4	Correct	4 ms	8280 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	8280 KB	Output is correct
9	Correct	3 ms	8280 KB	Output is correct
10	Correct	3 ms	8280 KB	Output is correct
11	Correct	3 ms	8284 KB	Output is correct
12	Correct	3 ms	8284 KB	Output is correct
13	Correct	3 ms	8284 KB	Output is correct
14	Correct	3 ms	8280 KB	Output is correct
15	Correct	3 ms	8284 KB	Output is correct
16	Correct	3 ms	8356 KB	Output is correct
17	Correct	3 ms	8284 KB	Output is correct
18	Correct	3 ms	8284 KB	Output is correct
19	Correct	4 ms	8284 KB	Output is correct
20	Correct	3 ms	8288 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	18648 KB	Output is correct
2	Correct	64 ms	18668 KB	Output is correct
3	Correct	79 ms	18640 KB	Output is correct
4	Correct	91 ms	18700 KB	Output is correct
5	Correct	70 ms	18512 KB	Output is correct
6	Correct	65 ms	27084 KB	Output is correct
7	Correct	67 ms	23896 KB	Output is correct
8	Correct	60 ms	22612 KB	Output is correct
9	Correct	63 ms	21076 KB	Output is correct
10	Correct	61 ms	18512 KB	Output is correct
11	Correct	56 ms	18516 KB	Output is correct
12	Correct	53 ms	18516 KB	Output is correct
13	Correct	64 ms	18528 KB	Output is correct
14	Correct	59 ms	18060 KB	Output is correct
15	Correct	41 ms	17492 KB	Output is correct
16	Correct	26 ms	14932 KB	Output is correct
17	Correct	41 ms	19080 KB	Output is correct
18	Correct	45 ms	19016 KB	Output is correct
19	Correct	47 ms	19144 KB	Output is correct
20	Correct	42 ms	19024 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	8288 KB	Output is correct
3	Incorrect	3 ms	8252 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	18516 KB	Output is correct
2	Correct	67 ms	18776 KB	Output is correct
3	Incorrect	65 ms	18000 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	8280 KB	Output is correct
2	Correct	2 ms	8284 KB	Output is correct
3	Correct	3 ms	8028 KB	Output is correct
4	Correct	3 ms	8284 KB	Output is correct
5	Correct	3 ms	8040 KB	Output is correct
6	Correct	2 ms	8028 KB	Output is correct
7	Incorrect	3 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	8280 KB	Output is correct
2	Correct	2 ms	8284 KB	Output is correct
3	Correct	3 ms	8028 KB	Output is correct
4	Correct	3 ms	8284 KB	Output is correct
5	Correct	3 ms	8040 KB	Output is correct
6	Correct	2 ms	8028 KB	Output is correct
7	Incorrect	3 ms	8284 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Submission #911540

Compilation message