oj.uz

Submission #158214

# Submission time Handle Problem Language Result Execution time Memory
158214 2019-10-15T14:01:37 Z maruii Duathlon (APIO18_duathlon) C++14
66 / 100
 145 ms 23752 KB 
#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);
	int v;
	for (auto i : bdge[x]) {
		if (i.ff == p) {
			v = i.ss;
			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];
	}
	if (p) ans -= 2 * (n - 1) * (N - sz[x]) * T[v];
	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, 0);
		bcc(i, ++cpnn);
		calc(cpnn, 0);
	}
	cout << ans;
	return 0;
}

Compilation message

count_triplets.cpp: In function 'void calc(int, int)':
count_triplets.cpp:56:47: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (p) ans -= 2 * (n - 1) * (N - sz[x]) * T[v];
                                            ~~~^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 4984 KB Output is correct
4 Correct 10 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Incorrect 8 ms 5112 KB Output isn't correct
9 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 6 ms 5112 KB Output is correct
3 Correct 7 ms 4984 KB Output is correct
4 Correct 10 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Incorrect 8 ms 5112 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 16848 KB Output is correct
2 Correct 89 ms 16752 KB Output is correct
3 Correct 82 ms 17272 KB Output is correct
4 Correct 77 ms 16376 KB Output is correct
5 Correct 74 ms 14968 KB Output is correct
6 Correct 145 ms 17816 KB Output is correct
7 Correct 85 ms 14748 KB Output is correct
8 Correct 101 ms 16268 KB Output is correct
9 Correct 86 ms 13816 KB Output is correct
10 Correct 80 ms 14072 KB Output is correct
11 Correct 77 ms 12448 KB Output is correct
12 Correct 63 ms 12280 KB Output is correct
13 Correct 59 ms 12280 KB Output is correct
14 Correct 60 ms 12140 KB Output is correct
15 Correct 47 ms 11896 KB Output is correct
16 Correct 49 ms 11700 KB Output is correct
17 Correct 10 ms 6904 KB Output is correct
18 Correct 10 ms 6904 KB Output is correct
19 Correct 10 ms 6908 KB Output is correct
20 Correct 10 ms 6904 KB Output is correct
21 Correct 10 ms 6776 KB Output is correct
22 Correct 11 ms 6904 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5116 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 8 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 7 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 5240 KB Output is correct
10 Correct 8 ms 5240 KB Output is correct
11 Correct 8 ms 5112 KB Output is correct
12 Correct 8 ms 5112 KB Output is correct
13 Correct 8 ms 5112 KB Output is correct
14 Correct 8 ms 5112 KB Output is correct
15 Correct 8 ms 5112 KB Output is correct
16 Correct 7 ms 5112 KB Output is correct
17 Correct 8 ms 5240 KB Output is correct
18 Correct 7 ms 5240 KB Output is correct
19 Correct 6 ms 5240 KB Output is correct
20 Correct 7 ms 5240 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 15072 KB Output is correct
2 Correct 89 ms 15224 KB Output is correct
3 Correct 91 ms 15140 KB Output is correct
4 Correct 88 ms 15096 KB Output is correct
5 Correct 88 ms 15052 KB Output is correct
6 Correct 125 ms 23752 KB Output is correct
7 Correct 111 ms 18204 KB Output is correct
8 Correct 113 ms 17320 KB Output is correct
9 Correct 110 ms 16544 KB Output is correct
10 Correct 86 ms 15116 KB Output is correct
11 Correct 86 ms 14968 KB Output is correct
12 Correct 89 ms 14896 KB Output is correct
13 Correct 85 ms 14968 KB Output is correct
14 Correct 75 ms 14456 KB Output is correct
15 Correct 74 ms 14072 KB Output is correct
16 Correct 52 ms 12408 KB Output is correct
17 Correct 63 ms 15084 KB Output is correct
18 Correct 62 ms 15084 KB Output is correct
19 Correct 70 ms 15220 KB Output is correct
20 Correct 67 ms 15148 KB Output is correct

Subtask #6
15.0 / 15.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 5112 KB Output is correct
5 Correct 7 ms 5160 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 6 ms 5112 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 5244 KB Output is correct
13 Correct 7 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 7 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Correct 6 ms 5112 KB Output is correct
19 Correct 7 ms 5084 KB Output is correct
20 Correct 6 ms 5112 KB Output is correct
21 Correct 7 ms 5112 KB Output is correct
22 Correct 7 ms 5112 KB Output is correct
23 Correct 6 ms 5112 KB Output is correct
24 Correct 6 ms 5160 KB Output is correct
25 Correct 6 ms 5112 KB Output is correct
26 Correct 6 ms 5112 KB Output is correct
27 Correct 6 ms 5112 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 15040 KB Output is correct
2 Correct 93 ms 14968 KB Output is correct
3 Correct 96 ms 13632 KB Output is correct
4 Correct 106 ms 12948 KB Output is correct
5 Correct 114 ms 12064 KB Output is correct
6 Correct 95 ms 11768 KB Output is correct
7 Correct 89 ms 11512 KB Output is correct
8 Correct 77 ms 11384 KB Output is correct
9 Correct 79 ms 11256 KB Output is correct
10 Correct 73 ms 11128 KB Output is correct
11 Correct 68 ms 11100 KB Output is correct
12 Correct 81 ms 11164 KB Output is correct
13 Correct 74 ms 11256 KB Output is correct
14 Correct 75 ms 12408 KB Output is correct
15 Correct 104 ms 16632 KB Output is correct
16 Correct 112 ms 15736 KB Output is correct
17 Correct 102 ms 15480 KB Output is correct
18 Correct 93 ms 14712 KB Output is correct
19 Correct 132 ms 12892 KB Output is correct
20 Correct 144 ms 12920 KB Output is correct
21 Correct 145 ms 12896 KB Output is correct
22 Correct 120 ms 12432 KB Output is correct
23 Correct 108 ms 12024 KB Output is correct
24 Correct 124 ms 14168 KB Output is correct
25 Correct 131 ms 14428 KB Output is correct
26 Correct 117 ms 13552 KB Output is correct
27 Correct 93 ms 13552 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 4984 KB Output is correct
4 Correct 10 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Incorrect 8 ms 5112 KB Output isn't correct
9 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 6 ms 5112 KB Output is correct
3 Correct 7 ms 4984 KB Output is correct
4 Correct 10 ms 4984 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Incorrect 8 ms 5112 KB Output isn't correct
9 Halted 0 ms 0 KB -