oj.uz

Submission #1073074

# Submission time Handle Problem Language Result Execution time Memory
1073074 2024-08-24T09:15:51 Z rainboy Telephone Plans (CCO24_day2problem3) C
11 / 25
 97 ms 13908 KB 
#include <stdio.h>

#define N	500000
#define Q	1500000

int tt[N + 1][2], pp[N + 1], sz[N + 1], sz_[N + 1]; char lz[N + 1];

int dir(int u) {
	return tt[pp[u]][0] == u ? 0 : 1;
}

int is_root(int u) {
	return tt[pp[u]][dir(u)] != u;
}

void put(int u) {
	if (u) {
		int tmp;

		tmp = tt[u][0], tt[u][0] = tt[u][1], tt[u][1] = tmp;
		lz[u] ^= 1;
	}
}

void pus(int u) {
	if (lz[u])
		put(tt[u][0]), put(tt[u][1]), lz[u] = 0;
}

void pul(int u) {
	sz[u] = sz[tt[u][0]] + sz_[u] + sz[tt[u][1]];
}

void attach(int u, int v, int d) {
	if (u)
		tt[u][d] = v, pul(u);
	if (v)
		pp[v] = u;
}

void rotate(int u) {
	int v, w, du, dv, isrt;

	v = pp[u], w = pp[v];
	pus(w), pus(v), pus(u);
	du = dir(u), dv = dir(v), isrt = is_root(v);
	attach(v, tt[u][du ^ 1], du);
	attach(u, v, du ^ 1);
	if (isrt)
		pp[u] = w;
	else
		attach(w, u, dv);
}

void splay(int u) {
	while (!is_root(u)) {
		int v = pp[u];

		if (!is_root(v))
			pus(v), rotate(dir(u) == dir(v) ? v : u);
		rotate(u);
	}
	pus(u);
}

void expose(int u) {
	int v, w;

	for (v = u, w = 0; v; w = v, v = pp[v]) {
		splay(v);
		sz_[v] += sz[tt[v][1]], attach(v, w, 1), sz_[v] -= sz[w];
		pul(v);
	}
	splay(u), put(u), pus(u);
}

long long m;

void link(int u, int v) {
	expose(u), expose(v);
	m += (long long) sz[u] * sz[v];
	sz_[u] += sz[tt[u][1]], attach(u, v, 1), pul(u);
}

void cut(int u, int v) {
	expose(u), expose(v);
	m -= (long long) sz_[v] * (sz[v] - sz_[v]);
	attach(v, 0, 1), pp[u] = 0;
}

int main() {
	static long long mm[Q + 1], ss[Q + 1];
	int n, q, h, encrypted, i, j, d, t, ans;
	long long i_, j_, d_;

	scanf("%d%d%d", &encrypted, &n, &q);
	for (i = 1; i <= n; i++)
		sz_[i] = 1;
	mm[0] = 0;
	ans = 0;
	for (h = 1; h <= q; h++) {
		scanf("%d", &t);
		if (t == 1) {
			scanf("%lld%lld", &i_, &j_);
			if (!encrypted)
				i = i_, j = j_;
			else
				i = i_ ^ ans, j = j_ ^ ans;
			link(i, j);
			mm[h] = m, ss[h] = ss[h - 1];
		} else if (t == 2) {
			scanf("%lld%lld", &i_, &j_);
			if (!encrypted)
				i = i_, j = j_;
			else
				i = i_ ^ ans, j = j_ ^ ans;
			cut(i, j);
			mm[h] = m, ss[h] = ss[h - 1] + mm[h - 1] - mm[h];
		} else {
			scanf("%lld", &d_);
			if (!encrypted)
				d = d_;
			else
				d = d_ ^ ans;
			mm[h] = m, ss[h] = ss[h - 1];
			printf("%d\n", ans = mm[h] + ss[h] - ss[h - d]);
		}
	}
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:96:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  scanf("%d%d%d", &encrypted, &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:102:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
Main.c:104:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |    scanf("%lld%lld", &i_, &j_);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:112:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |    scanf("%lld%lld", &i_, &j_);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:120:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |    scanf("%lld", &d_);
      |    ^~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 424 KB Output is correct
28 Correct 0 ms 348 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 2 ms 444 KB Output is correct
30 Correct 2 ms 608 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 2 ms 604 KB Output is correct
33 Correct 2 ms 600 KB Output is correct
34 Correct 2 ms 604 KB Output is correct
35 Correct 2 ms 436 KB Output is correct
36 Correct 2 ms 604 KB Output is correct
37 Correct 2 ms 604 KB Output is correct
38 Correct 1 ms 436 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 2 ms 660 KB Output is correct
41 Correct 2 ms 856 KB Output is correct
42 Correct 2 ms 604 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 1 ms 604 KB Output is correct
45 Correct 2 ms 604 KB Output is correct
46 Correct 3 ms 600 KB Output is correct
47 Correct 2 ms 604 KB Output is correct
48 Correct 2 ms 592 KB Output is correct
49 Correct 2 ms 604 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 424 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 2 ms 604 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 2 ms 604 KB Output is correct
33 Correct 2 ms 604 KB Output is correct
34 Correct 2 ms 604 KB Output is correct
35 Correct 2 ms 672 KB Output is correct
36 Correct 2 ms 604 KB Output is correct
37 Correct 2 ms 604 KB Output is correct
38 Correct 2 ms 604 KB Output is correct
39 Correct 2 ms 604 KB Output is correct
40 Correct 2 ms 604 KB Output is correct
41 Correct 2 ms 604 KB Output is correct
42 Correct 3 ms 604 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 2 ms 604 KB Output is correct
45 Correct 2 ms 604 KB Output is correct
46 Correct 3 ms 604 KB Output is correct
47 Correct 3 ms 604 KB Output is correct
48 Correct 2 ms 604 KB Output is correct
49 Correct 2 ms 604 KB Output is correct
50 Correct 2 ms 604 KB Output is correct
51 Correct 1 ms 604 KB Output is correct

Subtask #5
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 2 ms 444 KB Output is correct
30 Correct 2 ms 608 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 2 ms 604 KB Output is correct
33 Correct 2 ms 600 KB Output is correct
34 Correct 2 ms 604 KB Output is correct
35 Correct 2 ms 436 KB Output is correct
36 Correct 2 ms 604 KB Output is correct
37 Correct 2 ms 604 KB Output is correct
38 Correct 1 ms 436 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 2 ms 660 KB Output is correct
41 Correct 2 ms 856 KB Output is correct
42 Correct 2 ms 604 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 1 ms 604 KB Output is correct
45 Correct 2 ms 604 KB Output is correct
46 Correct 3 ms 600 KB Output is correct
47 Correct 2 ms 604 KB Output is correct
48 Correct 2 ms 592 KB Output is correct
49 Correct 2 ms 604 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Incorrect 66 ms 11604 KB Output isn't correct
53 Halted 0 ms 0 KB -

Subtask #6
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 424 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 2 ms 604 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 2 ms 604 KB Output is correct
33 Correct 2 ms 604 KB Output is correct
34 Correct 2 ms 604 KB Output is correct
35 Correct 2 ms 672 KB Output is correct
36 Correct 2 ms 604 KB Output is correct
37 Correct 2 ms 604 KB Output is correct
38 Correct 2 ms 604 KB Output is correct
39 Correct 2 ms 604 KB Output is correct
40 Correct 2 ms 604 KB Output is correct
41 Correct 2 ms 604 KB Output is correct
42 Correct 3 ms 604 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 2 ms 604 KB Output is correct
45 Correct 2 ms 604 KB Output is correct
46 Correct 3 ms 604 KB Output is correct
47 Correct 3 ms 604 KB Output is correct
48 Correct 2 ms 604 KB Output is correct
49 Correct 2 ms 604 KB Output is correct
50 Correct 2 ms 604 KB Output is correct
51 Correct 1 ms 604 KB Output is correct
52 Incorrect 97 ms 13908 KB Output isn't correct
53 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 424 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 2 ms 604 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 2 ms 604 KB Output is correct
33 Correct 2 ms 604 KB Output is correct
34 Correct 2 ms 604 KB Output is correct
35 Correct 2 ms 672 KB Output is correct
36 Correct 2 ms 604 KB Output is correct
37 Correct 2 ms 604 KB Output is correct
38 Correct 2 ms 604 KB Output is correct
39 Correct 2 ms 604 KB Output is correct
40 Correct 2 ms 604 KB Output is correct
41 Correct 2 ms 604 KB Output is correct
42 Correct 3 ms 604 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 2 ms 604 KB Output is correct
45 Correct 2 ms 604 KB Output is correct
46 Correct 3 ms 604 KB Output is correct
47 Correct 3 ms 604 KB Output is correct
48 Correct 2 ms 604 KB Output is correct
49 Correct 2 ms 604 KB Output is correct
50 Correct 2 ms 604 KB Output is correct
51 Correct 1 ms 604 KB Output is correct
52 Incorrect 97 ms 13908 KB Output isn't correct
53 Halted 0 ms 0 KB -