답안 #50911 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50911	2018-06-14T16:49:58 Z	Nicksechko	Birthday gift (IZhO18_treearray)	C++14	100 / 100	3233 ms	300008 KB

treearray

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #50911

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 18.0 / 18.0

Subtask #3 26.0 / 26.0

Subtask #4 44.0 / 44.0

Subtask #1
12.0 / 12.0

Subtask #2
18.0 / 18.0

Subtask #3
26.0 / 26.0

Subtask #4
44.0 / 44.0