Submission #158212

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
158212	2019-10-15T13:49:08 Z	maruii	Duathlon (APIO18_duathlon)	C++14	31 / 100	136 ms	23412 KB

count_triplets

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define ff first
#define ss second

int N, M, dfn[100005], dfnn, low[100005], cpn[100005], cpnn, sz[100005], T[100005];
vector<int> edge[100005];
vector<pii> 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].emplace_back(c, i);
			bdge[c].emplace_back(cpnn, x);
			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.ff == p) continue;
		calc(i.ff, x);
		ans -= 2 * (n - 1) * sz[i.ff] * T[i.ss];
		T[i.ss] += sz[i.ff];
		sz[x] += sz[i.ff];
		t -= 1ll * sz[i.ff] * sz[i.ff];
	}
	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	5012 KB	Output is correct
2	Correct	6 ms	4984 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	5116 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	5012 KB	Output is correct
2	Correct	6 ms	4984 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	5116 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	81 ms	16408 KB	Output is correct
2	Correct	76 ms	16416 KB	Output is correct
3	Correct	82 ms	17016 KB	Output is correct
4	Correct	136 ms	15992 KB	Output is correct
5	Correct	75 ms	14968 KB	Output is correct
6	Correct	89 ms	17864 KB	Output is correct
7	Correct	98 ms	14676 KB	Output is correct
8	Correct	85 ms	16120 KB	Output is correct
9	Correct	85 ms	13688 KB	Output is correct
10	Correct	75 ms	13944 KB	Output is correct
11	Correct	98 ms	12536 KB	Output is correct
12	Correct	63 ms	12408 KB	Output is correct
13	Correct	61 ms	12536 KB	Output is correct
14	Correct	57 ms	12280 KB	Output is correct
15	Correct	57 ms	12116 KB	Output is correct
16	Correct	47 ms	11816 KB	Output is correct
17	Correct	10 ms	7004 KB	Output is correct
18	Correct	10 ms	6904 KB	Output is correct
19	Correct	10 ms	6904 KB	Output is correct
20	Correct	10 ms	6904 KB	Output is correct
21	Correct	10 ms	6776 KB	Output is correct
22	Correct	9 ms	6780 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	86 ms	14728 KB	Output is correct
2	Correct	93 ms	14712 KB	Output is correct
3	Correct	79 ms	14712 KB	Output is correct
4	Correct	87 ms	14840 KB	Output is correct
5	Correct	88 ms	14712 KB	Output is correct
6	Correct	105 ms	23412 KB	Output is correct
7	Correct	94 ms	17784 KB	Output is correct
8	Correct	102 ms	16896 KB	Output is correct
9	Correct	96 ms	16092 KB	Output is correct
10	Correct	112 ms	14700 KB	Output is correct
11	Correct	88 ms	14840 KB	Output is correct
12	Correct	87 ms	14840 KB	Output is correct
13	Correct	88 ms	14840 KB	Output is correct
14	Correct	85 ms	14636 KB	Output is correct
15	Correct	74 ms	14200 KB	Output is correct
16	Correct	49 ms	12408 KB	Output is correct
17	Correct	67 ms	14936 KB	Output is correct
18	Correct	64 ms	15044 KB	Output is correct
19	Correct	65 ms	15176 KB	Output is correct
20	Correct	64 ms	15016 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	7 ms	5240 KB	Output is correct
3	Incorrect	8 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	85 ms	14712 KB	Output is correct
2	Correct	93 ms	14556 KB	Output is correct
3	Incorrect	133 ms	13208 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	5012 KB	Output is correct
2	Correct	6 ms	4984 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	5116 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	5012 KB	Output is correct
2	Correct	6 ms	4984 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	5116 KB	Output is correct
7	Incorrect	6 ms	4984 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Submission #158212

Compilation message