Submission #911754

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
911754	2024-01-19T05:06:25 Z	prairie2022	Duathlon (APIO18_duathlon)	C++17	31 / 100	104 ms	25440 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;

#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

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

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

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

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

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

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

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

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

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

Submission #911754

Compilation message