Submission #158204

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
158204	2019-10-15T13:30:00 Z	maruii	Duathlon (APIO18_duathlon)	C++14	31 / 100	144 ms	20616 KB

count_triplets

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N, M, dfn[100005], dfnn, low[100005], cpn[100005], cpnn, sz[100005];
vector<int> edge[100005], bdge[100005];
ll ans;

void dfs(int x, int p) {
	dfn[x] = low[x] = ++dfnn;
	N++;
	for (auto i : edge[x]) {
		if (i == p) continue;
		if (dfn[i]) {
			if (dfn[i] < dfn[x]) low[x] = min(low[x], dfn[i]);
			continue;
		}
		dfs(i, x);
		low[x] = min(low[x], low[i]);
	}
}

void bcc(int x, int c) {
	cpn[x] = c;
	sz[c]++;
	for (auto i : edge[x]) {
		if (cpn[i]) continue;
		if (low[i] == dfn[i]) {
			bdge[++cpnn].push_back(c);
			bdge[c].push_back(cpnn);
			bcc(i, cpnn);
		}
		else bcc(i, c);
	}
}

void calc(int x, int p) {
	ll n = sz[x], t = (N - n) * (N - n);
	ans += n * (n - 1) * (n - 2) + 2 * (n - 1) * (n - 1) * (N - n);
	for (auto i : bdge[x]) {
		if (i == p) continue;
		calc(i, x);
		sz[x] += sz[i];
		t -= 1ll * sz[i] * sz[i];
	}
	ans += n * (t - 1ll * (N - sz[x]) * (N - sz[x]));
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n >> M;
	for (int i = 0; i < M; ++i) {
		int x, y; cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	for (int i = 1; i <= n; ++i) {
		if (dfn[i]) continue;
		N = 0;
		dfs(i, i);
		bcc(i, ++cpnn);
		calc(cpnn, cpnn);
	}
	cout << ans;
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	9 ms	5116 KB	Output is correct
3	Correct	6 ms	4984 KB	Output is correct
4	Correct	6 ms	4984 KB	Output is correct
5	Correct	6 ms	4984 KB	Output is correct
6	Correct	6 ms	4984 KB	Output is correct
7	Incorrect	6 ms	4984 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	86 ms	15608 KB	Output is correct
2	Correct	95 ms	15724 KB	Output is correct
3	Correct	102 ms	15056 KB	Output is correct
4	Correct	92 ms	14840 KB	Output is correct
5	Correct	84 ms	14328 KB	Output is correct
6	Correct	83 ms	16888 KB	Output is correct
7	Correct	85 ms	14200 KB	Output is correct
8	Correct	96 ms	15564 KB	Output is correct
9	Correct	88 ms	13560 KB	Output is correct
10	Correct	92 ms	13696 KB	Output is correct
11	Correct	65 ms	12280 KB	Output is correct
12	Correct	66 ms	12152 KB	Output is correct
13	Correct	63 ms	12152 KB	Output is correct
14	Correct	58 ms	11908 KB	Output is correct
15	Correct	53 ms	11772 KB	Output is correct
16	Correct	52 ms	11324 KB	Output is correct
17	Correct	9 ms	6608 KB	Output is correct
18	Correct	9 ms	6616 KB	Output is correct
19	Correct	9 ms	6652 KB	Output is correct
20	Correct	9 ms	6648 KB	Output is correct
21	Correct	9 ms	6648 KB	Output is correct
22	Correct	11 ms	6648 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	13064 KB	Output is correct
2	Correct	86 ms	13120 KB	Output is correct
3	Correct	134 ms	13020 KB	Output is correct
4	Correct	83 ms	13048 KB	Output is correct
5	Correct	89 ms	13176 KB	Output is correct
6	Correct	144 ms	20616 KB	Output is correct
7	Correct	99 ms	15736 KB	Output is correct
8	Correct	84 ms	14956 KB	Output is correct
9	Correct	83 ms	14328 KB	Output is correct
10	Correct	86 ms	13048 KB	Output is correct
11	Correct	90 ms	14328 KB	Output is correct
12	Correct	81 ms	14328 KB	Output is correct
13	Correct	91 ms	14328 KB	Output is correct
14	Correct	74 ms	13944 KB	Output is correct
15	Correct	75 ms	13688 KB	Output is correct
16	Correct	47 ms	11896 KB	Output is correct
17	Correct	69 ms	14912 KB	Output is correct
18	Correct	74 ms	14960 KB	Output is correct
19	Correct	63 ms	14956 KB	Output is correct
20	Correct	67 ms	14844 KB	Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	13048 KB	Output is correct
2	Correct	98 ms	12984 KB	Output is correct
3	Incorrect	90 ms	11896 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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

Submission #158204

Compilation message