Submission #216360

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
216360	2020-03-27T08:17:14 Z	theStaticMind	Duathlon (APIO18_duathlon)	C++14	31 / 100	924 ms	1048580 KB

count_triplets

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

vector<int> adj[300005];
vector<int> sub(300005, 0);
vector<bool> vis(300005, false);
vector<bool> mark(300005, false);
int ans = 0;

void dfs(int x, int pre){
	sub[x] = 1;
	vis[x] = true;
	for(auto y : adj[x]){
		if(y == pre) continue;
		if(vis[y]){
			mark[y] = true;
			continue;
		}
		dfs(y, x);
		sub[x] += sub[y];
	}
}

void calc(int x, int pre, int sum){
	ans += 2ll * (sub[x] - 1) * (sum - sub[x]);

	int w = 0;

	for(auto y : adj[x]){
		if(y == pre) continue;
		ans += 2ll * sub[y] * w;
		w += sub[y];
	}

	for(auto y : adj[x]){
		if(y == pre) continue;
		calc(y, x, sum);
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m;
	cin >> n >> m;

	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	vector<int> root;
	for(int i = 1; i <= n; i++){
		if(sub[i] == 0) dfs(i, -1), root.pb(i);
	}
	for(auto r : root){ 
		if(!mark[r]) calc(r, -1, sub[r]);
		else ans += sub[r] * (sub[r] - 1) * (sub[r] - 2);
	}

	cout << ans;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9856 KB	Output is correct
2	Correct	10 ms	9856 KB	Output is correct
3	Correct	10 ms	9856 KB	Output is correct
4	Correct	10 ms	9856 KB	Output is correct
5	Correct	10 ms	9728 KB	Output is correct
6	Correct	10 ms	9856 KB	Output is correct
7	Incorrect	10 ms	9856 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9856 KB	Output is correct
2	Correct	10 ms	9856 KB	Output is correct
3	Correct	10 ms	9856 KB	Output is correct
4	Correct	10 ms	9856 KB	Output is correct
5	Correct	10 ms	9728 KB	Output is correct
6	Correct	10 ms	9856 KB	Output is correct
7	Incorrect	10 ms	9856 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	72 ms	20728 KB	Output is correct
2	Correct	76 ms	20752 KB	Output is correct
3	Correct	90 ms	16888 KB	Output is correct
4	Correct	75 ms	20088 KB	Output is correct
5	Correct	84 ms	16864 KB	Output is correct
6	Correct	73 ms	16888 KB	Output is correct
7	Correct	84 ms	15796 KB	Output is correct
8	Correct	72 ms	16376 KB	Output is correct
9	Correct	73 ms	14968 KB	Output is correct
10	Correct	76 ms	15736 KB	Output is correct
11	Correct	62 ms	14712 KB	Output is correct
12	Correct	60 ms	14200 KB	Output is correct
13	Correct	55 ms	14452 KB	Output is correct
14	Correct	53 ms	14324 KB	Output is correct
15	Correct	41 ms	13688 KB	Output is correct
16	Correct	40 ms	13688 KB	Output is correct
17	Correct	14 ms	11000 KB	Output is correct
18	Correct	12 ms	11000 KB	Output is correct
19	Correct	12 ms	11000 KB	Output is correct
20	Correct	12 ms	11000 KB	Output is correct
21	Correct	12 ms	11000 KB	Output is correct
22	Correct	12 ms	11000 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9856 KB	Output is correct
2	Correct	10 ms	9856 KB	Output is correct
3	Correct	11 ms	9856 KB	Output is correct
4	Correct	10 ms	9856 KB	Output is correct
5	Correct	10 ms	9856 KB	Output is correct
6	Correct	10 ms	9856 KB	Output is correct
7	Correct	10 ms	9856 KB	Output is correct
8	Correct	10 ms	9856 KB	Output is correct
9	Correct	10 ms	9856 KB	Output is correct
10	Correct	10 ms	9856 KB	Output is correct
11	Correct	14 ms	9844 KB	Output is correct
12	Correct	10 ms	9856 KB	Output is correct
13	Correct	10 ms	9856 KB	Output is correct
14	Correct	10 ms	9856 KB	Output is correct
15	Correct	10 ms	9856 KB	Output is correct
16	Correct	10 ms	9856 KB	Output is correct
17	Correct	11 ms	9856 KB	Output is correct
18	Correct	10 ms	9856 KB	Output is correct
19	Correct	10 ms	9856 KB	Output is correct
20	Correct	10 ms	9856 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	13560 KB	Output is correct
2	Correct	65 ms	13560 KB	Output is correct
3	Correct	75 ms	13568 KB	Output is correct
4	Correct	67 ms	13560 KB	Output is correct
5	Correct	67 ms	13560 KB	Output is correct
6	Correct	91 ms	17136 KB	Output is correct
7	Correct	79 ms	16376 KB	Output is correct
8	Correct	81 ms	15608 KB	Output is correct
9	Correct	72 ms	14840 KB	Output is correct
10	Correct	66 ms	13552 KB	Output is correct
11	Correct	95 ms	13560 KB	Output is correct
12	Correct	67 ms	13560 KB	Output is correct
13	Correct	68 ms	13560 KB	Output is correct
14	Correct	66 ms	13560 KB	Output is correct
15	Correct	56 ms	13432 KB	Output is correct
16	Correct	38 ms	12920 KB	Output is correct
17	Correct	58 ms	13676 KB	Output is correct
18	Correct	46 ms	13672 KB	Output is correct
19	Correct	46 ms	13932 KB	Output is correct
20	Correct	46 ms	13672 KB	Output is correct

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9856 KB	Output is correct
2	Correct	10 ms	9856 KB	Output is correct
3	Runtime error	789 ms	1048576 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	13816 KB	Output is correct
2	Correct	69 ms	13688 KB	Output is correct
3	Runtime error	924 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9856 KB	Output is correct
2	Correct	10 ms	9856 KB	Output is correct
3	Correct	10 ms	9856 KB	Output is correct
4	Correct	10 ms	9856 KB	Output is correct
5	Correct	10 ms	9728 KB	Output is correct
6	Correct	10 ms	9856 KB	Output is correct
7	Incorrect	10 ms	9856 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	9856 KB	Output is correct
2	Correct	10 ms	9856 KB	Output is correct
3	Correct	10 ms	9856 KB	Output is correct
4	Correct	10 ms	9856 KB	Output is correct
5	Correct	10 ms	9728 KB	Output is correct
6	Correct	10 ms	9856 KB	Output is correct
7	Incorrect	10 ms	9856 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Submission #216360

Compilation message