oj.uz

Submission #50911

# Submission time Handle Problem Language Result Execution time Memory
50911 2018-06-14T16:49:58 Z Nicksechko Birthday gift (IZhO18_treearray) C++14
100 / 100
 3233 ms 300008 KB 
#ifndef LOCAL
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

typedef long long ll;
typedef long long llong;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;

/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int LOG = 20;
const int MAXN = 220000;

int tin[MAXN];
int tout[MAXN];

int up[LOG][MAXN];

vector<int> eds[MAXN];
set<int> g1[MAXN];
set<int> g2[MAXN];
int tm1;
int a[MAXN];

int n, m, q;

void dfs1(int v, int p) {
	tin[v] = tm1++;
	for (int u: eds[v]) {
		if (u == p)
			continue;
		up[0][u] = v;
		dfs1(u, v);
	}
	tout[v] = tm1;
}

int is_p(int a, int b) {
	return tin[a] <= tin[b] && tin[b] < tout[a];
}

int lca(int a, int b) {
	if (is_p(a, b))
		return a;
	for (int i = LOG - 1; i >= 0; --i) {
		if (!is_p(up[i][a], b))
			a = up[i][a];
	}
	return up[0][a];
}


int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	for (int i = 0; i < m; ++i) {
		scanf("%d", a + i);
		--a[i];
	}
	dfs1(0, -1);
	for (int i = 1; i < LOG; ++i) {
		for (int j = 0; j < n; ++j)
			up[i][j] = up[i - 1][up[i - 1][j]];
	}
	for (int i = 0; i < m; ++i) {
		g1[a[i]].insert(i);
		if (i < m - 1)
			g2[lca(a[i], a[i + 1])].insert(i);
	}
	for (int i = 0; i < q; ++i) {
		int t;
		scanf("%d", &t);
		if (t == 1) {
			int ps, v;
			scanf("%d%d", &ps, &v);
			--ps, --v;
			g1[a[ps]].erase(ps);
			if (ps < m - 1)
				g2[lca(a[ps], a[ps + 1])].erase(ps);
			if (ps > 0)
				g2[lca(a[ps], a[ps - 1])].erase(ps - 1);
			a[ps] = v;
			g1[a[ps]].insert(ps);
			if (ps < m - 1)
				g2[lca(a[ps], a[ps + 1])].insert(ps);
			if (ps > 0)
				g2[lca(a[ps], a[ps - 1])].insert(ps - 1);
		}
		else {
			int l, r, v;
			scanf("%d%d%d", &l, &r, &v);
			--l, --r, --v;
			auto it1 = g1[v].lower_bound(l);
			if (it1 != g1[v].end() && *it1 <= r) {
				printf("%d %d\n", *it1 + 1, *it1 + 1);
			}
			else {
				auto it2 = g2[v].lower_bound(l);
				if (it2 != g2[v].end() && *it2 < r) {
					printf("%d %d\n", *it2 + 1, *it2 + 1 + 1);
				}
				else {
					printf("-1 -1\n");
				}
			}
		}
	}
	return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~
treearray.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
treearray.cpp:92:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &ps, &v);
    ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d", &l, &r, &v);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26232 KB n=5
2 Correct 24 ms 26344 KB n=100
3 Correct 25 ms 26456 KB n=100
4 Correct 25 ms 26456 KB n=100
5 Correct 25 ms 26456 KB n=100
6 Correct 24 ms 26488 KB n=100
7 Correct 25 ms 26536 KB n=100
8 Correct 26 ms 26536 KB n=100
9 Correct 24 ms 26540 KB n=100
10 Correct 26 ms 26548 KB n=100
11 Correct 24 ms 26552 KB n=100
12 Correct 24 ms 26684 KB n=100
13 Correct 25 ms 26684 KB n=100
14 Correct 26 ms 26684 KB n=100
15 Correct 27 ms 26684 KB n=100
16 Correct 27 ms 26684 KB n=100
17 Correct 24 ms 26684 KB n=100
18 Correct 24 ms 26756 KB n=100
19 Correct 24 ms 26756 KB n=100
20 Correct 24 ms 26756 KB n=100
21 Correct 24 ms 26756 KB n=100
22 Correct 25 ms 26784 KB n=100
23 Correct 24 ms 26784 KB n=100
24 Correct 24 ms 26792 KB n=100
25 Correct 24 ms 26796 KB n=100
26 Correct 24 ms 26796 KB n=12
27 Correct 24 ms 26796 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26232 KB n=5
2 Correct 24 ms 26344 KB n=100
3 Correct 25 ms 26456 KB n=100
4 Correct 25 ms 26456 KB n=100
5 Correct 25 ms 26456 KB n=100
6 Correct 24 ms 26488 KB n=100
7 Correct 25 ms 26536 KB n=100
8 Correct 26 ms 26536 KB n=100
9 Correct 24 ms 26540 KB n=100
10 Correct 26 ms 26548 KB n=100
11 Correct 24 ms 26552 KB n=100
12 Correct 24 ms 26684 KB n=100
13 Correct 25 ms 26684 KB n=100
14 Correct 26 ms 26684 KB n=100
15 Correct 27 ms 26684 KB n=100
16 Correct 27 ms 26684 KB n=100
17 Correct 24 ms 26684 KB n=100
18 Correct 24 ms 26756 KB n=100
19 Correct 24 ms 26756 KB n=100
20 Correct 24 ms 26756 KB n=100
21 Correct 24 ms 26756 KB n=100
22 Correct 25 ms 26784 KB n=100
23 Correct 24 ms 26784 KB n=100
24 Correct 24 ms 26792 KB n=100
25 Correct 24 ms 26796 KB n=100
26 Correct 24 ms 26796 KB n=12
27 Correct 24 ms 26796 KB n=100
28 Correct 25 ms 26808 KB n=500
29 Correct 25 ms 26940 KB n=500
30 Correct 29 ms 26940 KB n=500
31 Correct 25 ms 26940 KB n=500
32 Correct 26 ms 26940 KB n=500
33 Correct 25 ms 26940 KB n=500
34 Correct 26 ms 26944 KB n=500
35 Correct 25 ms 26952 KB n=500
36 Correct 25 ms 26988 KB n=500
37 Correct 25 ms 27000 KB n=500
38 Correct 27 ms 27048 KB n=500
39 Correct 25 ms 27048 KB n=500
40 Correct 25 ms 27048 KB n=500
41 Correct 25 ms 27056 KB n=500
42 Correct 25 ms 27072 KB n=500
43 Correct 25 ms 27116 KB n=500
44 Correct 30 ms 27116 KB n=500
45 Correct 30 ms 27116 KB n=500
46 Correct 25 ms 27120 KB n=500
47 Correct 25 ms 27136 KB n=500
48 Correct 26 ms 27156 KB n=500
49 Correct 29 ms 27168 KB n=500
50 Correct 26 ms 27184 KB n=500
51 Correct 26 ms 27196 KB n=500
52 Correct 25 ms 27212 KB n=500
53 Correct 25 ms 27236 KB n=500
54 Correct 25 ms 27244 KB n=500
55 Correct 25 ms 27292 KB n=278
56 Correct 25 ms 27292 KB n=500
57 Correct 32 ms 27292 KB n=500
58 Correct 25 ms 27308 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26232 KB n=5
2 Correct 24 ms 26344 KB n=100
3 Correct 25 ms 26456 KB n=100
4 Correct 25 ms 26456 KB n=100
5 Correct 25 ms 26456 KB n=100
6 Correct 24 ms 26488 KB n=100
7 Correct 25 ms 26536 KB n=100
8 Correct 26 ms 26536 KB n=100
9 Correct 24 ms 26540 KB n=100
10 Correct 26 ms 26548 KB n=100
11 Correct 24 ms 26552 KB n=100
12 Correct 24 ms 26684 KB n=100
13 Correct 25 ms 26684 KB n=100
14 Correct 26 ms 26684 KB n=100
15 Correct 27 ms 26684 KB n=100
16 Correct 27 ms 26684 KB n=100
17 Correct 24 ms 26684 KB n=100
18 Correct 24 ms 26756 KB n=100
19 Correct 24 ms 26756 KB n=100
20 Correct 24 ms 26756 KB n=100
21 Correct 24 ms 26756 KB n=100
22 Correct 25 ms 26784 KB n=100
23 Correct 24 ms 26784 KB n=100
24 Correct 24 ms 26792 KB n=100
25 Correct 24 ms 26796 KB n=100
26 Correct 24 ms 26796 KB n=12
27 Correct 24 ms 26796 KB n=100
28 Correct 25 ms 26808 KB n=500
29 Correct 25 ms 26940 KB n=500
30 Correct 29 ms 26940 KB n=500
31 Correct 25 ms 26940 KB n=500
32 Correct 26 ms 26940 KB n=500
33 Correct 25 ms 26940 KB n=500
34 Correct 26 ms 26944 KB n=500
35 Correct 25 ms 26952 KB n=500
36 Correct 25 ms 26988 KB n=500
37 Correct 25 ms 27000 KB n=500
38 Correct 27 ms 27048 KB n=500
39 Correct 25 ms 27048 KB n=500
40 Correct 25 ms 27048 KB n=500
41 Correct 25 ms 27056 KB n=500
42 Correct 25 ms 27072 KB n=500
43 Correct 25 ms 27116 KB n=500
44 Correct 30 ms 27116 KB n=500
45 Correct 30 ms 27116 KB n=500
46 Correct 25 ms 27120 KB n=500
47 Correct 25 ms 27136 KB n=500
48 Correct 26 ms 27156 KB n=500
49 Correct 29 ms 27168 KB n=500
50 Correct 26 ms 27184 KB n=500
51 Correct 26 ms 27196 KB n=500
52 Correct 25 ms 27212 KB n=500
53 Correct 25 ms 27236 KB n=500
54 Correct 25 ms 27244 KB n=500
55 Correct 25 ms 27292 KB n=278
56 Correct 25 ms 27292 KB n=500
57 Correct 32 ms 27292 KB n=500
58 Correct 25 ms 27308 KB n=500
59 Correct 29 ms 27732 KB n=2000
60 Correct 29 ms 27868 KB n=2000
61 Correct 30 ms 27868 KB n=2000
62 Correct 30 ms 27868 KB n=2000
63 Correct 30 ms 27908 KB n=2000
64 Correct 31 ms 27960 KB n=2000
65 Correct 31 ms 28020 KB n=2000
66 Correct 29 ms 28072 KB n=2000
67 Correct 31 ms 28128 KB n=2000
68 Correct 30 ms 28184 KB n=2000
69 Correct 28 ms 28368 KB n=2000
70 Correct 28 ms 28368 KB n=2000
71 Correct 28 ms 28424 KB n=2000
72 Correct 27 ms 28424 KB n=2000
73 Correct 39 ms 28452 KB n=2000
74 Correct 35 ms 28508 KB n=1844
75 Correct 29 ms 28552 KB n=2000
76 Correct 29 ms 28608 KB n=2000
77 Correct 30 ms 28660 KB n=2000
78 Correct 30 ms 28712 KB n=2000
79 Correct 29 ms 28764 KB n=2000
80 Correct 29 ms 28868 KB n=2000
81 Correct 30 ms 28928 KB n=2000
82 Correct 30 ms 28928 KB n=2000
83 Correct 29 ms 28972 KB n=2000
84 Correct 29 ms 29028 KB n=2000
85 Correct 30 ms 29080 KB n=2000
86 Correct 30 ms 29136 KB n=2000
87 Correct 29 ms 29192 KB n=2000
88 Correct 28 ms 29372 KB n=2000
89 Correct 29 ms 29428 KB n=2000
90 Correct 32 ms 29428 KB n=2000
91 Correct 28 ms 29428 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26232 KB n=5
2 Correct 24 ms 26344 KB n=100
3 Correct 25 ms 26456 KB n=100
4 Correct 25 ms 26456 KB n=100
5 Correct 25 ms 26456 KB n=100
6 Correct 24 ms 26488 KB n=100
7 Correct 25 ms 26536 KB n=100
8 Correct 26 ms 26536 KB n=100
9 Correct 24 ms 26540 KB n=100
10 Correct 26 ms 26548 KB n=100
11 Correct 24 ms 26552 KB n=100
12 Correct 24 ms 26684 KB n=100
13 Correct 25 ms 26684 KB n=100
14 Correct 26 ms 26684 KB n=100
15 Correct 27 ms 26684 KB n=100
16 Correct 27 ms 26684 KB n=100
17 Correct 24 ms 26684 KB n=100
18 Correct 24 ms 26756 KB n=100
19 Correct 24 ms 26756 KB n=100
20 Correct 24 ms 26756 KB n=100
21 Correct 24 ms 26756 KB n=100
22 Correct 25 ms 26784 KB n=100
23 Correct 24 ms 26784 KB n=100
24 Correct 24 ms 26792 KB n=100
25 Correct 24 ms 26796 KB n=100
26 Correct 24 ms 26796 KB n=12
27 Correct 24 ms 26796 KB n=100
28 Correct 25 ms 26808 KB n=500
29 Correct 25 ms 26940 KB n=500
30 Correct 29 ms 26940 KB n=500
31 Correct 25 ms 26940 KB n=500
32 Correct 26 ms 26940 KB n=500
33 Correct 25 ms 26940 KB n=500
34 Correct 26 ms 26944 KB n=500
35 Correct 25 ms 26952 KB n=500
36 Correct 25 ms 26988 KB n=500
37 Correct 25 ms 27000 KB n=500
38 Correct 27 ms 27048 KB n=500
39 Correct 25 ms 27048 KB n=500
40 Correct 25 ms 27048 KB n=500
41 Correct 25 ms 27056 KB n=500
42 Correct 25 ms 27072 KB n=500
43 Correct 25 ms 27116 KB n=500
44 Correct 30 ms 27116 KB n=500
45 Correct 30 ms 27116 KB n=500
46 Correct 25 ms 27120 KB n=500
47 Correct 25 ms 27136 KB n=500
48 Correct 26 ms 27156 KB n=500
49 Correct 29 ms 27168 KB n=500
50 Correct 26 ms 27184 KB n=500
51 Correct 26 ms 27196 KB n=500
52 Correct 25 ms 27212 KB n=500
53 Correct 25 ms 27236 KB n=500
54 Correct 25 ms 27244 KB n=500
55 Correct 25 ms 27292 KB n=278
56 Correct 25 ms 27292 KB n=500
57 Correct 32 ms 27292 KB n=500
58 Correct 25 ms 27308 KB n=500
59 Correct 29 ms 27732 KB n=2000
60 Correct 29 ms 27868 KB n=2000
61 Correct 30 ms 27868 KB n=2000
62 Correct 30 ms 27868 KB n=2000
63 Correct 30 ms 27908 KB n=2000
64 Correct 31 ms 27960 KB n=2000
65 Correct 31 ms 28020 KB n=2000
66 Correct 29 ms 28072 KB n=2000
67 Correct 31 ms 28128 KB n=2000
68 Correct 30 ms 28184 KB n=2000
69 Correct 28 ms 28368 KB n=2000
70 Correct 28 ms 28368 KB n=2000
71 Correct 28 ms 28424 KB n=2000
72 Correct 27 ms 28424 KB n=2000
73 Correct 39 ms 28452 KB n=2000
74 Correct 35 ms 28508 KB n=1844
75 Correct 29 ms 28552 KB n=2000
76 Correct 29 ms 28608 KB n=2000
77 Correct 30 ms 28660 KB n=2000
78 Correct 30 ms 28712 KB n=2000
79 Correct 29 ms 28764 KB n=2000
80 Correct 29 ms 28868 KB n=2000
81 Correct 30 ms 28928 KB n=2000
82 Correct 30 ms 28928 KB n=2000
83 Correct 29 ms 28972 KB n=2000
84 Correct 29 ms 29028 KB n=2000
85 Correct 30 ms 29080 KB n=2000
86 Correct 30 ms 29136 KB n=2000
87 Correct 29 ms 29192 KB n=2000
88 Correct 28 ms 29372 KB n=2000
89 Correct 29 ms 29428 KB n=2000
90 Correct 32 ms 29428 KB n=2000
91 Correct 28 ms 29428 KB n=2000
92 Correct 2157 ms 80640 KB n=200000
93 Correct 2082 ms 90356 KB n=200000
94 Correct 1863 ms 100304 KB n=200000
95 Correct 1979 ms 102204 KB n=200000
96 Correct 2036 ms 108872 KB n=200000
97 Correct 1999 ms 118124 KB n=200000
98 Correct 1939 ms 123024 KB n=200000
99 Correct 2011 ms 129504 KB n=200000
100 Correct 1943 ms 136668 KB n=200000
101 Correct 1965 ms 149708 KB n=200000
102 Correct 1176 ms 151940 KB n=200000
103 Correct 1159 ms 158628 KB n=200000
104 Correct 973 ms 165284 KB n=200000
105 Correct 917 ms 172320 KB n=200000
106 Correct 952 ms 179752 KB n=200000
107 Correct 971 ms 187256 KB n=200000
108 Correct 1838 ms 192920 KB n=200000
109 Correct 1789 ms 199916 KB n=200000
110 Correct 1788 ms 206684 KB n=200000
111 Correct 1785 ms 213032 KB n=200000
112 Correct 1826 ms 225428 KB n=200000
113 Correct 2188 ms 230168 KB n=200000
114 Correct 2178 ms 234392 KB n=200000
115 Correct 3233 ms 242464 KB n=200000
116 Correct 2188 ms 248848 KB n=200000
117 Correct 2001 ms 261696 KB n=200000
118 Correct 2621 ms 265552 KB n=200000
119 Correct 2113 ms 271064 KB n=200000
120 Correct 1738 ms 283616 KB n=200000
121 Correct 1899 ms 290452 KB n=200000
122 Correct 2036 ms 297660 KB n=200000
123 Correct 1097 ms 300008 KB n=200000
124 Correct 463 ms 300008 KB n=25264