oj.uz

Submission #432083

# Submission time Handle Problem Language Result Execution time Memory
432083 2021-06-17T20:18:36 Z rainboy Simurgh (IOI17_simurgh) C++
100 / 100
 1026 ms 5584 KB 
#include "simurgh.h"
#include <stdlib.h>
#include <string.h>

using namespace std;

const int N = 500, M = N * (N - 1) / 2;

typedef vector<int> vi;

int ds[N], n;

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

int join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

int ii[M], jj[M];
int *eh[N], eo[N];

void append(int i, int h) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

char cc[M], marked[M];

int dfs(int p, int i, int t) {
	int o;

	if (i == t)
		return 1;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ii[h] ^ jj[h];

		if (j != p && dfs(i, j, t)) {
			marked[h] = 1;
			return 1;
		}
	}
	return 0;
}

vi hh, hh_;
int k_;

int count(int i, int m) {
	int g, m_, k;

	memset(ds, -1, n * sizeof *ds);
	m_ = 0;
	for (g = 0; g < m; g++) {
		int h = eh[i][g];

		join(ii[h], jj[h]);
		hh_[m_++] = h;
	}
	k = 0;
	for (g = 0; g < n - 1; g++)
		if (join(ii[hh[g]], jj[hh[g]]))
			hh_[m_++] = hh[g];
		else if (cc[hh[g]])
			k++;
	return count_common_roads(hh_) - k_ + k;
}

void solve(int i, int l, int r, int a, int b) {
	int m, c;

	if (a == b)
		return;
	if (r - l == 1) {
		cc[eh[i][l]] = 1;
		return;
	}
	m = (l + r) / 2;
	c = count(i, m);
	solve(i, l, m, a, c), solve(i, m, r, c, b);
}

vi find_roads(int n_, vi ii_, vi jj_) {
	int m = ii_.size(), m_, g, h, i;

	n = n_;
	for (h = 0; h < m; h++)
		ii[h] = ii_[h], jj[h] = jj_[h];
	hh.resize(n - 1), hh_.resize(n - 1);
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	m_ = 0;
	for (h = 0; h < m; h++)
		if (join(ii[h], jj[h])) {
			hh[m_++] = h, cc[h] = -1;
			append(ii[h], h), append(jj[h], h);
		} else
			cc[h] = -2;
	k_ = count_common_roads(hh);
	for (h = 0; h < m; h++) {
		int upd, c, tmp, k;

		if (cc[h] != -2)
			continue;
		for (g = 0; g < n - 1; g++)
			marked[hh[g]] = 0;
		dfs(-1, ii[h], jj[h]);
		upd = 0;
		for (g = 0; g < n - 1; g++)
			if (marked[hh[g]] && cc[hh[g]] == -1) {
				upd = 1;
				break;
			}
		if (!upd)
			continue;
		c = -1;
		for (g = 0; g < n - 1; g++)
			if (marked[hh[g]] && cc[hh[g]] != -1) {
				tmp = hh[g], hh[g] = h, k = count_common_roads(hh), hh[g] = tmp;
				c = cc[hh[g]] ^ (k == k_ ? 0 : 1);
				break;
			}
		for (g = 0; g < n - 1; g++)
			if (marked[hh[g]] && cc[hh[g]] == -1) {
				tmp = hh[g], hh[g] = h, k = count_common_roads(hh), hh[g] = tmp;
				if (k == k_ + 1)
					c = 1;
				else if (k == k_ - 1)
					c = 0;
				if (c != -1)
					cc[hh[g]] = c ^ (k == k_ ? 0 : 1);
			}
		if (c == -1)
			c = 0;
		for (g = 0; g < n - 1; g++)
			if (marked[hh[g]] && cc[hh[g]] == -1)
				cc[hh[g]] = c;
	}
	for (h = 0; h < m; h++)
		if (cc[h] == -1)
			cc[h] = 1;
		else if (cc[h] == -2)
			append(ii[h], h), append(jj[h], h);
	for (i = 0; i < n; i++) {
		int o, o_;

		for (o = 0, o_ = 0; o < eo[i]; o++) {
			h = eh[i][o];
			if (cc[h] == -2)
				cc[h] = 0, eh[i][o_++] = h;
		}
		eo[i] = o_;
		solve(i, 0, eo[i], 0, count(i, eo[i]));
	}
	m_ = 0;
	for (h = 0; h < m; h++)
		if (cc[h] == 1)
			hh[m_++] = h;
	return hh;
}

Compilation message

simurgh.cpp: In function 'void append(int, int)':
simurgh.cpp:38:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   38 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB correct
2 Correct 2 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 2 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 220 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 204 KB correct
9 Correct 0 ms 204 KB correct
10 Correct 0 ms 204 KB correct
11 Correct 0 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 0 ms 204 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB correct
2 Correct 2 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 2 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 220 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 204 KB correct
9 Correct 0 ms 204 KB correct
10 Correct 0 ms 204 KB correct
11 Correct 0 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 0 ms 204 KB correct
14 Correct 3 ms 332 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 332 KB correct
18 Correct 1 ms 204 KB correct
19 Correct 2 ms 332 KB correct
20 Correct 3 ms 384 KB correct
21 Correct 3 ms 332 KB correct
22 Correct 2 ms 332 KB correct
23 Correct 2 ms 332 KB correct
24 Correct 1 ms 332 KB correct
25 Correct 1 ms 204 KB correct
26 Correct 1 ms 332 KB correct
27 Correct 2 ms 332 KB correct
28 Correct 1 ms 256 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 332 KB correct
31 Correct 2 ms 332 KB correct
32 Correct 2 ms 332 KB correct
33 Correct 2 ms 332 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB correct
2 Correct 2 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 2 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 220 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 204 KB correct
9 Correct 0 ms 204 KB correct
10 Correct 0 ms 204 KB correct
11 Correct 0 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 0 ms 204 KB correct
14 Correct 3 ms 332 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 332 KB correct
18 Correct 1 ms 204 KB correct
19 Correct 2 ms 332 KB correct
20 Correct 3 ms 384 KB correct
21 Correct 3 ms 332 KB correct
22 Correct 2 ms 332 KB correct
23 Correct 2 ms 332 KB correct
24 Correct 1 ms 332 KB correct
25 Correct 1 ms 204 KB correct
26 Correct 1 ms 332 KB correct
27 Correct 2 ms 332 KB correct
28 Correct 1 ms 256 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 332 KB correct
31 Correct 2 ms 332 KB correct
32 Correct 2 ms 332 KB correct
33 Correct 2 ms 332 KB correct
34 Correct 123 ms 1264 KB correct
35 Correct 119 ms 1272 KB correct
36 Correct 83 ms 1032 KB correct
37 Correct 12 ms 332 KB correct
38 Correct 123 ms 1376 KB correct
39 Correct 99 ms 1144 KB correct
40 Correct 79 ms 1020 KB correct
41 Correct 120 ms 1220 KB correct
42 Correct 113 ms 1252 KB correct
43 Correct 48 ms 920 KB correct
44 Correct 40 ms 708 KB correct
45 Correct 43 ms 780 KB correct
46 Correct 35 ms 716 KB correct
47 Correct 18 ms 436 KB correct
48 Correct 5 ms 320 KB correct
49 Correct 10 ms 332 KB correct
50 Correct 18 ms 436 KB correct
51 Correct 48 ms 780 KB correct
52 Correct 42 ms 732 KB correct
53 Correct 34 ms 572 KB correct
54 Correct 49 ms 792 KB correct
55 Correct 49 ms 780 KB correct
56 Correct 58 ms 784 KB correct
57 Correct 58 ms 812 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 0 ms 204 KB correct
3 Correct 495 ms 3176 KB correct
4 Correct 970 ms 5456 KB correct
5 Correct 999 ms 5460 KB correct
6 Correct 927 ms 5456 KB correct
7 Correct 955 ms 5460 KB correct
8 Correct 917 ms 5584 KB correct
9 Correct 936 ms 5472 KB correct
10 Correct 943 ms 5452 KB correct
11 Correct 970 ms 5460 KB correct
12 Correct 961 ms 5464 KB correct
13 Correct 0 ms 204 KB correct
14 Correct 982 ms 5476 KB correct
15 Correct 1026 ms 5464 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB correct
2 Correct 2 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 2 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 220 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 204 KB correct
9 Correct 0 ms 204 KB correct
10 Correct 0 ms 204 KB correct
11 Correct 0 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 0 ms 204 KB correct
14 Correct 3 ms 332 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 332 KB correct
18 Correct 1 ms 204 KB correct
19 Correct 2 ms 332 KB correct
20 Correct 3 ms 384 KB correct
21 Correct 3 ms 332 KB correct
22 Correct 2 ms 332 KB correct
23 Correct 2 ms 332 KB correct
24 Correct 1 ms 332 KB correct
25 Correct 1 ms 204 KB correct
26 Correct 1 ms 332 KB correct
27 Correct 2 ms 332 KB correct
28 Correct 1 ms 256 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 332 KB correct
31 Correct 2 ms 332 KB correct
32 Correct 2 ms 332 KB correct
33 Correct 2 ms 332 KB correct
34 Correct 123 ms 1264 KB correct
35 Correct 119 ms 1272 KB correct
36 Correct 83 ms 1032 KB correct
37 Correct 12 ms 332 KB correct
38 Correct 123 ms 1376 KB correct
39 Correct 99 ms 1144 KB correct
40 Correct 79 ms 1020 KB correct
41 Correct 120 ms 1220 KB correct
42 Correct 113 ms 1252 KB correct
43 Correct 48 ms 920 KB correct
44 Correct 40 ms 708 KB correct
45 Correct 43 ms 780 KB correct
46 Correct 35 ms 716 KB correct
47 Correct 18 ms 436 KB correct
48 Correct 5 ms 320 KB correct
49 Correct 10 ms 332 KB correct
50 Correct 18 ms 436 KB correct
51 Correct 48 ms 780 KB correct
52 Correct 42 ms 732 KB correct
53 Correct 34 ms 572 KB correct
54 Correct 49 ms 792 KB correct
55 Correct 49 ms 780 KB correct
56 Correct 58 ms 784 KB correct
57 Correct 58 ms 812 KB correct
58 Correct 1 ms 204 KB correct
59 Correct 0 ms 204 KB correct
60 Correct 495 ms 3176 KB correct
61 Correct 970 ms 5456 KB correct
62 Correct 999 ms 5460 KB correct
63 Correct 927 ms 5456 KB correct
64 Correct 955 ms 5460 KB correct
65 Correct 917 ms 5584 KB correct
66 Correct 936 ms 5472 KB correct
67 Correct 943 ms 5452 KB correct
68 Correct 970 ms 5460 KB correct
69 Correct 961 ms 5464 KB correct
70 Correct 0 ms 204 KB correct
71 Correct 982 ms 5476 KB correct
72 Correct 1026 ms 5464 KB correct
73 Correct 1 ms 204 KB correct
74 Correct 981 ms 5460 KB correct
75 Correct 979 ms 5444 KB correct
76 Correct 303 ms 2132 KB correct
77 Correct 942 ms 5460 KB correct
78 Correct 1004 ms 5584 KB correct
79 Correct 977 ms 5456 KB correct
80 Correct 918 ms 5344 KB correct
81 Correct 772 ms 4792 KB correct
82 Correct 919 ms 5320 KB correct
83 Correct 560 ms 2936 KB correct
84 Correct 513 ms 3572 KB correct
85 Correct 463 ms 3304 KB correct
86 Correct 296 ms 2304 KB correct
87 Correct 221 ms 1832 KB correct
88 Correct 173 ms 1348 KB correct
89 Correct 188 ms 1288 KB correct
90 Correct 146 ms 1220 KB correct
91 Correct 29 ms 448 KB correct
92 Correct 18 ms 300 KB correct
93 Correct 441 ms 3336 KB correct
94 Correct 315 ms 2348 KB correct
95 Correct 296 ms 2180 KB correct
96 Correct 146 ms 1220 KB correct
97 Correct 164 ms 1304 KB correct
98 Correct 224 ms 1828 KB correct
99 Correct 214 ms 1416 KB correct
100 Correct 55 ms 580 KB correct
101 Correct 18 ms 388 KB correct
102 Correct 433 ms 2848 KB correct
103 Correct 431 ms 2840 KB correct
104 Correct 426 ms 2892 KB correct
105 Correct 442 ms 2892 KB correct