Submission #252389

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
252389	2020-07-25T12:35:13 Z	Saboon	Duathlon (APIO18_duathlon)	C++14	36 / 100	650 ms	1048580 KB

count_triplets

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 20;
const int mod = 1e9 + 7;

vector<int> g[maxn], t[maxn];
int dw[maxn], h[maxn], rt[maxn], a[maxn], sz[maxn];
bool visited[maxn];
int sz2[maxn];
ll answer = 0;

void dfs2(int v, int par = -1){
	sz2[v] = a[v];
	for (auto u : t[v]){
		if (u != par){
			dfs2(u, v);
			sz2[v] += sz2[u];
			answer += 1ll * sz2[u] * (sz[rt[v]] - sz2[u] - a[v]);
		}
	}
	if (par != -1)
		answer += 1ll * (sz2[v] - a[v]) * (sz[rt[v]] - sz2[v]);
}

int dfs(int v, int root){
	rt[v] = root;
	visited[v] = true;
	int ret = h[v];
	sz[v] = 1;
	dw[v] = v;
	a[v] = 1;
	for (auto u : g[v]){
		if (!visited[u]){
			h[u] = h[v] + 1;
			int k = dfs(u, root);
			sz[v] += sz[u];
			if (k <= h[v]){
				a[v] = a[u];
				dw[v] = dw[u];
			}
			ret = min(ret, k);
		}
		else if (h[u] < h[v] - 1){
			dw[v] = v;
			a[v] = h[v] - h[u] + 1;
			ret = h[u];
		}
	}
	return ret;
}

int adj[12][12], dp[2000][12];

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	if (n <= 10){
		for (int i = 1; i <= m; i++){
			int v, u;
			cin >> v >> u;
			v --, u --;
			adj[v][u] = adj[u][v] = 1;
		}
		int answer = 0;
		for (int s = 0; s < n; s++){
			for (int c = 0; c < n; c++){
				if (c == s)
					continue;
				for (int f = 0; f < n; f++){
					if (f == c or f == s)
						continue;
					memset(dp, 0, sizeof dp);
					dp[(1 << s)][s] = 1;
					bool found = 0;
					for (int mask = (1<<s)+1; mask < (1 << n); mask++){
						for (int i = 0; i < n; i++){
							if (!(mask & (1 << i)))
								continue;
							for (int j = 0; j < n; j++)
								dp[mask][i] |= (adj[i][j] & dp[mask^(1<<i)][j]);
						}
						if (mask & (1 << s) and mask & (1 << c) and dp[mask][f])
							found = 1;
					}
					answer += found;
				}
			}
		}
		cout << answer << endl;
		return 0;
	}
	for (int i = 0; i < m; i++){
		int v, u;
		cin >> v >> u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	for (int v = 1; v <= n; v++)
		if (!visited[v])
			dfs(v, v);
	for (int i = 1; i <= n; i++)
		for (auto j : g[i])
			if (dw[i] != dw[j])
				t[dw[i]].push_back(dw[j]);
	for (int v = 1; v <= n; v++)
		if (h[v] == 0)
			dfs2(dw[v]);
	for (int v = 1; v <= n; v++)
		if (dw[v] == v and a[v] >= 3)
			answer -= 1ll*a[v]*(a[v]-1)*(a[v]-2);
	for (int f = 1; f <= n; f++){
		if (a[dw[f]] == 1)
			continue;
		int subsz = 1;
		for (auto u : g[f]){
			if (h[u] == h[f]+1 and dw[u] != dw[f])
				subsz += sz[u];
			if (h[u] == h[f]-1 and dw[u] != dw[f])
				subsz += (sz[rt[f]] - sz[f]);
		}
		int outsz = sz[rt[f]] - subsz;
		answer += 2ll * (a[dw[f]]-1) * (outsz-1);
	}
	cout << answer << endl;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	14464 KB	Output is correct
2	Correct	9 ms	14464 KB	Output is correct
3	Correct	9 ms	14464 KB	Output is correct
4	Correct	8 ms	14464 KB	Output is correct
5	Correct	8 ms	14464 KB	Output is correct
6	Correct	65 ms	14568 KB	Output is correct
7	Correct	65 ms	14464 KB	Output is correct
8	Correct	65 ms	14464 KB	Output is correct
9	Correct	65 ms	14464 KB	Output is correct
10	Correct	68 ms	14584 KB	Output is correct
11	Correct	65 ms	14516 KB	Output is correct
12	Correct	65 ms	14464 KB	Output is correct
13	Correct	71 ms	14572 KB	Output is correct
14	Correct	66 ms	14464 KB	Output is correct
15	Correct	70 ms	14584 KB	Output is correct
16	Correct	64 ms	14464 KB	Output is correct
17	Correct	65 ms	14464 KB	Output is correct
18	Correct	66 ms	14464 KB	Output is correct
19	Correct	64 ms	14592 KB	Output is correct
20	Correct	65 ms	14464 KB	Output is correct
21	Correct	66 ms	14464 KB	Output is correct
22	Correct	66 ms	14464 KB	Output is correct
23	Correct	26 ms	14464 KB	Output is correct
24	Correct	13 ms	14464 KB	Output is correct
25	Correct	26 ms	14592 KB	Output is correct
26	Correct	65 ms	14464 KB	Output is correct
27	Correct	13 ms	14464 KB	Output is correct
28	Correct	26 ms	14464 KB	Output is correct
29	Correct	64 ms	14464 KB	Output is correct
30	Correct	13 ms	14464 KB	Output is correct
31	Correct	25 ms	14464 KB	Output is correct
32	Correct	65 ms	14464 KB	Output is correct
33	Correct	27 ms	14464 KB	Output is correct
34	Correct	26 ms	14464 KB	Output is correct
35	Correct	65 ms	14464 KB	Output is correct

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	14464 KB	Output is correct
2	Correct	9 ms	14464 KB	Output is correct
3	Correct	9 ms	14464 KB	Output is correct
4	Correct	8 ms	14464 KB	Output is correct
5	Correct	8 ms	14464 KB	Output is correct
6	Correct	65 ms	14568 KB	Output is correct
7	Correct	65 ms	14464 KB	Output is correct
8	Correct	65 ms	14464 KB	Output is correct
9	Correct	65 ms	14464 KB	Output is correct
10	Correct	68 ms	14584 KB	Output is correct
11	Correct	65 ms	14516 KB	Output is correct
12	Correct	65 ms	14464 KB	Output is correct
13	Correct	71 ms	14572 KB	Output is correct
14	Correct	66 ms	14464 KB	Output is correct
15	Correct	70 ms	14584 KB	Output is correct
16	Correct	64 ms	14464 KB	Output is correct
17	Correct	65 ms	14464 KB	Output is correct
18	Correct	66 ms	14464 KB	Output is correct
19	Correct	64 ms	14592 KB	Output is correct
20	Correct	65 ms	14464 KB	Output is correct
21	Correct	66 ms	14464 KB	Output is correct
22	Correct	66 ms	14464 KB	Output is correct
23	Correct	26 ms	14464 KB	Output is correct
24	Correct	13 ms	14464 KB	Output is correct
25	Correct	26 ms	14592 KB	Output is correct
26	Correct	65 ms	14464 KB	Output is correct
27	Correct	13 ms	14464 KB	Output is correct
28	Correct	26 ms	14464 KB	Output is correct
29	Correct	64 ms	14464 KB	Output is correct
30	Correct	13 ms	14464 KB	Output is correct
31	Correct	25 ms	14464 KB	Output is correct
32	Correct	65 ms	14464 KB	Output is correct
33	Correct	27 ms	14464 KB	Output is correct
34	Correct	26 ms	14464 KB	Output is correct
35	Correct	65 ms	14464 KB	Output is correct
36	Correct	8 ms	14464 KB	Output is correct
37	Correct	9 ms	14464 KB	Output is correct
38	Runtime error	650 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
39	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	27512 KB	Output is correct
2	Correct	79 ms	27460 KB	Output is correct
3	Correct	95 ms	25464 KB	Output is correct
4	Correct	92 ms	26744 KB	Output is correct
5	Correct	83 ms	23672 KB	Output is correct
6	Correct	91 ms	24312 KB	Output is correct
7	Correct	90 ms	23544 KB	Output is correct
8	Correct	94 ms	24060 KB	Output is correct
9	Correct	91 ms	22648 KB	Output is correct
10	Correct	84 ms	23032 KB	Output is correct
11	Correct	70 ms	21628 KB	Output is correct
12	Correct	74 ms	21628 KB	Output is correct
13	Correct	78 ms	21624 KB	Output is correct
14	Correct	74 ms	21496 KB	Output is correct
15	Correct	57 ms	21368 KB	Output is correct
16	Correct	62 ms	20984 KB	Output is correct
17	Correct	15 ms	16896 KB	Output is correct
18	Correct	11 ms	16896 KB	Output is correct
19	Correct	15 ms	16768 KB	Output is correct
20	Correct	10 ms	16768 KB	Output is correct
21	Correct	10 ms	16768 KB	Output is correct
22	Correct	10 ms	16768 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	23416 KB	Output is correct
2	Correct	83 ms	23416 KB	Output is correct
3	Correct	83 ms	23416 KB	Output is correct
4	Correct	87 ms	23416 KB	Output is correct
5	Correct	83 ms	23420 KB	Output is correct
6	Correct	100 ms	27384 KB	Output is correct
7	Correct	99 ms	25976 KB	Output is correct
8	Correct	111 ms	25336 KB	Output is correct
9	Correct	105 ms	24568 KB	Output is correct
10	Correct	85 ms	23416 KB	Output is correct
11	Correct	85 ms	23416 KB	Output is correct
12	Correct	82 ms	23416 KB	Output is correct
13	Correct	88 ms	23416 KB	Output is correct
14	Correct	76 ms	23160 KB	Output is correct
15	Correct	69 ms	23016 KB	Output is correct
16	Correct	48 ms	21624 KB	Output is correct
17	Correct	64 ms	23920 KB	Output is correct
18	Correct	60 ms	23920 KB	Output is correct
19	Correct	63 ms	24048 KB	Output is correct
20	Correct	66 ms	23928 KB	Output is correct

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	14592 KB	Output is correct
2	Correct	8 ms	14592 KB	Output is correct
3	Incorrect	9 ms	14592 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	23336 KB	Output is correct
2	Correct	107 ms	23420 KB	Output is correct
3	Incorrect	130 ms	22264 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	14464 KB	Output is correct
2	Correct	9 ms	14464 KB	Output is correct
3	Correct	9 ms	14464 KB	Output is correct
4	Correct	8 ms	14464 KB	Output is correct
5	Correct	8 ms	14464 KB	Output is correct
6	Correct	65 ms	14568 KB	Output is correct
7	Correct	65 ms	14464 KB	Output is correct
8	Correct	65 ms	14464 KB	Output is correct
9	Correct	65 ms	14464 KB	Output is correct
10	Correct	68 ms	14584 KB	Output is correct
11	Correct	65 ms	14516 KB	Output is correct
12	Correct	65 ms	14464 KB	Output is correct
13	Correct	71 ms	14572 KB	Output is correct
14	Correct	66 ms	14464 KB	Output is correct
15	Correct	70 ms	14584 KB	Output is correct
16	Correct	64 ms	14464 KB	Output is correct
17	Correct	65 ms	14464 KB	Output is correct
18	Correct	66 ms	14464 KB	Output is correct
19	Correct	64 ms	14592 KB	Output is correct
20	Correct	65 ms	14464 KB	Output is correct
21	Correct	66 ms	14464 KB	Output is correct
22	Correct	66 ms	14464 KB	Output is correct
23	Correct	26 ms	14464 KB	Output is correct
24	Correct	13 ms	14464 KB	Output is correct
25	Correct	26 ms	14592 KB	Output is correct
26	Correct	65 ms	14464 KB	Output is correct
27	Correct	13 ms	14464 KB	Output is correct
28	Correct	26 ms	14464 KB	Output is correct
29	Correct	64 ms	14464 KB	Output is correct
30	Correct	13 ms	14464 KB	Output is correct
31	Correct	25 ms	14464 KB	Output is correct
32	Correct	65 ms	14464 KB	Output is correct
33	Correct	27 ms	14464 KB	Output is correct
34	Correct	26 ms	14464 KB	Output is correct
35	Correct	65 ms	14464 KB	Output is correct
36	Correct	8 ms	14464 KB	Output is correct
37	Correct	9 ms	14464 KB	Output is correct
38	Runtime error	650 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
39	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	14464 KB	Output is correct
2	Correct	9 ms	14464 KB	Output is correct
3	Correct	9 ms	14464 KB	Output is correct
4	Correct	8 ms	14464 KB	Output is correct
5	Correct	8 ms	14464 KB	Output is correct
6	Correct	65 ms	14568 KB	Output is correct
7	Correct	65 ms	14464 KB	Output is correct
8	Correct	65 ms	14464 KB	Output is correct
9	Correct	65 ms	14464 KB	Output is correct
10	Correct	68 ms	14584 KB	Output is correct
11	Correct	65 ms	14516 KB	Output is correct
12	Correct	65 ms	14464 KB	Output is correct
13	Correct	71 ms	14572 KB	Output is correct
14	Correct	66 ms	14464 KB	Output is correct
15	Correct	70 ms	14584 KB	Output is correct
16	Correct	64 ms	14464 KB	Output is correct
17	Correct	65 ms	14464 KB	Output is correct
18	Correct	66 ms	14464 KB	Output is correct
19	Correct	64 ms	14592 KB	Output is correct
20	Correct	65 ms	14464 KB	Output is correct
21	Correct	66 ms	14464 KB	Output is correct
22	Correct	66 ms	14464 KB	Output is correct
23	Correct	26 ms	14464 KB	Output is correct
24	Correct	13 ms	14464 KB	Output is correct
25	Correct	26 ms	14592 KB	Output is correct
26	Correct	65 ms	14464 KB	Output is correct
27	Correct	13 ms	14464 KB	Output is correct
28	Correct	26 ms	14464 KB	Output is correct
29	Correct	64 ms	14464 KB	Output is correct
30	Correct	13 ms	14464 KB	Output is correct
31	Correct	25 ms	14464 KB	Output is correct
32	Correct	65 ms	14464 KB	Output is correct
33	Correct	27 ms	14464 KB	Output is correct
34	Correct	26 ms	14464 KB	Output is correct
35	Correct	65 ms	14464 KB	Output is correct
36	Correct	8 ms	14464 KB	Output is correct
37	Correct	9 ms	14464 KB	Output is correct
38	Runtime error	650 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
39	Halted	0 ms	0 KB	-

Submission #252389

Compilation message