oj.uz

Submission #241705

# Submission time Handle Problem Language Result Execution time Memory
241705 2020-06-25T09:44:03 Z atoiz Duathlon (APIO18_duathlon) C++14
0 / 100
 72 ms 17412 KB 
/*input
4 4
1 2
2 3
3 4
4 2

4 3
1 2
3 4
4 1

5 4
1 2
2 3
3 4
4 5

4 3
1 2
2 3
3 4

*/

#include <stdio.h>

#define N 100007
#define M 400007
int n, m, to[M], nx[M], st[N], low[N], vis[N], ts, stk[N], instack[N], *top = &stk[0];
int bto[N * 4], bnx[N * 4], bst[N * 2], b, bm, bsz[N * 2];
long long ans = 0;

inline void minimize(int &i, int j) { (i > j ? i = j : 0); }

void build(int u, int p)
{
	low[u] = vis[u] = ++ts;
	instack[*(++top) = u] = 1;

	int i, v, w, c = 0;
	for (i = st[u]; i; i = nx[i]) if (to[i] != p) {
		v = to[i];
		if (!vis[v]) {
			++c;
			build(v, u);
			if (low[v] >= vis[u]) {
				++b;
				bool cont = true;
				while (cont) {
					instack[w = (*top--)] = 0;
					cont = (w != v);
					++bm, bnx[bm] = bst[w], bto[bst[w] = bm] = b;
					++bm, bnx[bm] = bst[b], bto[bst[b] = bm] = w;
				}
				++bm, bnx[bm] = bst[b], bto[bst[b] = bm] = u;
				++bm, bnx[bm] = bst[u], bto[bst[u] = bm] = b;
			}
			minimize(low[u], low[v]);
		} else if (instack[v]) {
			minimize(low[u], vis[v]);
		}
	}
}

void solve(int u, int p)
{
	int i, v, d = 0;
	long long x = 0;

	bsz[u] = (u <= n);
	for (i = bst[u]; i; i = bnx[i]) if (bto[i] != p) {
		solve(v = bto[i], u), bsz[u] += bsz[v], ++d;
		x += (long long) bsz[v] * (bsz[v] - 1);
	}

	if (u > n) {
		x += (long long) (n - bsz[u]) * (n - bsz[u] - 1);
		ans -= x * d;
	}
}

int main()
{
	int i, u, v;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; ++i) {
		scanf("%d %d", &u, &v);
		nx[i * 2] = st[u], to[st[u] = i * 2] = v;
		nx[i * 2 - 1] = st[v], to[st[v] = i * 2 - 1] = u;
	}

	b = n, build(1, 0);
	ans = (long long) n * (n - 1) * (n - 2), solve(1, 0);
	printf("%lld", ans);
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16124 KB Output is correct
2 Correct 70 ms 16120 KB Output is correct
3 Incorrect 44 ms 10360 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 8744 KB Output is correct
2 Correct 53 ms 8696 KB Output is correct
3 Correct 49 ms 8696 KB Output is correct
4 Correct 49 ms 8696 KB Output is correct
5 Correct 52 ms 8696 KB Output is correct
6 Correct 63 ms 17412 KB Output is correct
7 Correct 58 ms 14456 KB Output is correct
8 Correct 60 ms 13068 KB Output is correct
9 Correct 52 ms 11512 KB Output is correct
10 Incorrect 45 ms 6904 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 6 ms 512 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8696 KB Output is correct
2 Correct 51 ms 8684 KB Output is correct
3 Correct 57 ms 8568 KB Output is correct
4 Correct 59 ms 9080 KB Output is correct
5 Correct 53 ms 8312 KB Output is correct
6 Correct 50 ms 7928 KB Output is correct
7 Correct 49 ms 7800 KB Output is correct
8 Correct 47 ms 7548 KB Output is correct
9 Correct 49 ms 7464 KB Output is correct
10 Correct 48 ms 7416 KB Output is correct
11 Correct 46 ms 7288 KB Output is correct
12 Correct 47 ms 7416 KB Output is correct
13 Correct 48 ms 7416 KB Output is correct
14 Correct 56 ms 9124 KB Output is correct
15 Correct 72 ms 15608 KB Output is correct
16 Correct 69 ms 13564 KB Output is correct
17 Correct 67 ms 14456 KB Output is correct
18 Correct 64 ms 12664 KB Output is correct
19 Incorrect 56 ms 8824 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -