oj.uz

Submission #42686

# Submission time Handle Problem Language Result Execution time Memory
42686 2018-03-02T16:34:16 Z bash Birthday gift (IZhO18_treearray) C++14
100 / 100
 1688 ms 262144 KB 
/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <bits/stdc++.h>

#define F first
#define S second
#define endl '\n'
#define pb push_back

const long long MOD = 1e9 + 7;
const long long SZ = 18;
const long long MAXN = 1e6 + 1;
const int MXN = 2e5 +777;
using namespace std;

typedef long long ll;

long long readInt() {
    bool minus1 = false;
    long long result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus1 = true; else result = ch-'0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus1)          
        return -result;
    else
        return result;
}

int a[MAXN];

set <int> L[MXN]; 

set <int> cnt[MXN];

int lvl[MAXN];
vector <int> g[MAXN];
int up[MAXN][SZ];
int d[MAXN];

int dfs(int v, int par) {
    lvl[v] = lvl[par] + 1;
    up[v][0] = par;
    for (int i = 1; i < SZ; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    d[v] = 1;
    for (auto i : g[v]) {
        if (i == par) continue;
        dfs(i, v);
        d[v] += d[i];
    }
}
int lca(int a, int b) {
    if (lvl[a] > lvl[b]) swap(a, b);
    for (int i = SZ - 1; i >= 0; i--) {
        if (lvl[up[b][i]] >= lvl[a]) {
            b = up[b][i];
        }
    }
    if (a == b) return a;
    for (int i = SZ - 1; i >= 0; i--) {
        if (up[b][i] != up[a][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

int main() {
	#ifdef IZI_KATKA
	assert(freopen("input", "r", stdin));
    assert(freopen("output", "w", stdout));
    #endif
    int n = readInt(), m = readInt(), q = readInt();
    for (int i = 1; i < n; i ++) {
    	int u = readInt(), v = readInt();
    	g[u].pb(v);
    	g[v].pb(u);
    }
    dfs(1, 0);
	for (int i = 1; i <= m; i++) {
		a[i] =  readInt();
		cnt[a[i]].insert(i);

		if (i != 1) {
			L[lca(a[i], a[i - 1])].insert(i-1);				
		}
	}
    while(q--) {
    	int type = readInt();
    	if (type == 1) {
			int pos = readInt(), v = readInt();
			cnt[a[pos]].erase(pos);
			if (pos != 1) {
				L[lca(a[pos - 1], a[pos])].erase(pos - 1);
			}
			if (pos != n) {
				L[lca(a[pos], a[pos + 1])].erase(pos);
			}
			a[pos] = v;
			cnt[v].insert(pos);
			if (pos != 1) {
			    L[lca(a[pos - 1], a[pos])].insert(pos - 1);
			} 
			if (pos != n) {
				L[lca(a[pos], a[pos + 1])].insert(pos);
			}
    	} else {
    		int l = readInt(), r = readInt(), v = readInt(); 	
        	if (!cnt[v].empty()) {
				auto i = cnt[v].lower_bound(l);
				if (i != cnt[v].end()) {
					int ans = *i;
					if (ans <= r) {
						cout << ans << ' ' << ans << endl;
						continue;				
					}
				}
			}
			if (!L[v].empty()) {
				auto i = L[v].lower_bound(l);
				if (i != L[v].end()) {
					int ans = *i;
					if (ans +1<= r) {
						cout << ans << ' ' << ans+1 << endl;					
				    	continue;
					}
				}
			} 
			cout << "-1 -1\n";
    	}
    }
    return 0;
}

Compilation message

treearray.cpp: In function 'int dfs(int, int)':
treearray.cpp:64:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 42620 KB n=5
2 Correct 36 ms 42720 KB n=100
3 Correct 35 ms 42760 KB n=100
4 Correct 35 ms 42764 KB n=100
5 Correct 34 ms 42896 KB n=100
6 Correct 34 ms 42896 KB n=100
7 Correct 36 ms 42984 KB n=100
8 Correct 35 ms 43096 KB n=100
9 Correct 36 ms 43096 KB n=100
10 Correct 35 ms 43100 KB n=100
11 Correct 35 ms 43128 KB n=100
12 Correct 43 ms 43128 KB n=100
13 Correct 36 ms 43128 KB n=100
14 Correct 34 ms 43128 KB n=100
15 Correct 38 ms 43128 KB n=100
16 Correct 37 ms 43148 KB n=100
17 Correct 37 ms 43148 KB n=100
18 Correct 37 ms 43148 KB n=100
19 Correct 35 ms 43148 KB n=100
20 Correct 37 ms 43148 KB n=100
21 Correct 39 ms 43168 KB n=100
22 Correct 36 ms 43168 KB n=100
23 Correct 36 ms 43168 KB n=100
24 Correct 36 ms 43168 KB n=100
25 Correct 34 ms 43168 KB n=100
26 Correct 39 ms 43168 KB n=12
27 Correct 37 ms 43168 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 42620 KB n=5
2 Correct 36 ms 42720 KB n=100
3 Correct 35 ms 42760 KB n=100
4 Correct 35 ms 42764 KB n=100
5 Correct 34 ms 42896 KB n=100
6 Correct 34 ms 42896 KB n=100
7 Correct 36 ms 42984 KB n=100
8 Correct 35 ms 43096 KB n=100
9 Correct 36 ms 43096 KB n=100
10 Correct 35 ms 43100 KB n=100
11 Correct 35 ms 43128 KB n=100
12 Correct 43 ms 43128 KB n=100
13 Correct 36 ms 43128 KB n=100
14 Correct 34 ms 43128 KB n=100
15 Correct 38 ms 43128 KB n=100
16 Correct 37 ms 43148 KB n=100
17 Correct 37 ms 43148 KB n=100
18 Correct 37 ms 43148 KB n=100
19 Correct 35 ms 43148 KB n=100
20 Correct 37 ms 43148 KB n=100
21 Correct 39 ms 43168 KB n=100
22 Correct 36 ms 43168 KB n=100
23 Correct 36 ms 43168 KB n=100
24 Correct 36 ms 43168 KB n=100
25 Correct 34 ms 43168 KB n=100
26 Correct 39 ms 43168 KB n=12
27 Correct 37 ms 43168 KB n=100
28 Correct 37 ms 43168 KB n=500
29 Correct 36 ms 43208 KB n=500
30 Correct 38 ms 43240 KB n=500
31 Correct 38 ms 43272 KB n=500
32 Correct 37 ms 43272 KB n=500
33 Correct 38 ms 43276 KB n=500
34 Correct 37 ms 43296 KB n=500
35 Correct 35 ms 43432 KB n=500
36 Correct 36 ms 43432 KB n=500
37 Correct 37 ms 43460 KB n=500
38 Correct 36 ms 43460 KB n=500
39 Correct 34 ms 43500 KB n=500
40 Correct 35 ms 43500 KB n=500
41 Correct 36 ms 43500 KB n=500
42 Correct 34 ms 43500 KB n=500
43 Correct 35 ms 43500 KB n=500
44 Correct 37 ms 43500 KB n=500
45 Correct 37 ms 43604 KB n=500
46 Correct 37 ms 43616 KB n=500
47 Correct 35 ms 43632 KB n=500
48 Correct 34 ms 43632 KB n=500
49 Correct 36 ms 43676 KB n=500
50 Correct 38 ms 43676 KB n=500
51 Correct 36 ms 43688 KB n=500
52 Correct 37 ms 43704 KB n=500
53 Correct 36 ms 43760 KB n=500
54 Correct 38 ms 43760 KB n=500
55 Correct 35 ms 43760 KB n=278
56 Correct 37 ms 43788 KB n=500
57 Correct 39 ms 43804 KB n=500
58 Correct 35 ms 43804 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 42620 KB n=5
2 Correct 36 ms 42720 KB n=100
3 Correct 35 ms 42760 KB n=100
4 Correct 35 ms 42764 KB n=100
5 Correct 34 ms 42896 KB n=100
6 Correct 34 ms 42896 KB n=100
7 Correct 36 ms 42984 KB n=100
8 Correct 35 ms 43096 KB n=100
9 Correct 36 ms 43096 KB n=100
10 Correct 35 ms 43100 KB n=100
11 Correct 35 ms 43128 KB n=100
12 Correct 43 ms 43128 KB n=100
13 Correct 36 ms 43128 KB n=100
14 Correct 34 ms 43128 KB n=100
15 Correct 38 ms 43128 KB n=100
16 Correct 37 ms 43148 KB n=100
17 Correct 37 ms 43148 KB n=100
18 Correct 37 ms 43148 KB n=100
19 Correct 35 ms 43148 KB n=100
20 Correct 37 ms 43148 KB n=100
21 Correct 39 ms 43168 KB n=100
22 Correct 36 ms 43168 KB n=100
23 Correct 36 ms 43168 KB n=100
24 Correct 36 ms 43168 KB n=100
25 Correct 34 ms 43168 KB n=100
26 Correct 39 ms 43168 KB n=12
27 Correct 37 ms 43168 KB n=100
28 Correct 37 ms 43168 KB n=500
29 Correct 36 ms 43208 KB n=500
30 Correct 38 ms 43240 KB n=500
31 Correct 38 ms 43272 KB n=500
32 Correct 37 ms 43272 KB n=500
33 Correct 38 ms 43276 KB n=500
34 Correct 37 ms 43296 KB n=500
35 Correct 35 ms 43432 KB n=500
36 Correct 36 ms 43432 KB n=500
37 Correct 37 ms 43460 KB n=500
38 Correct 36 ms 43460 KB n=500
39 Correct 34 ms 43500 KB n=500
40 Correct 35 ms 43500 KB n=500
41 Correct 36 ms 43500 KB n=500
42 Correct 34 ms 43500 KB n=500
43 Correct 35 ms 43500 KB n=500
44 Correct 37 ms 43500 KB n=500
45 Correct 37 ms 43604 KB n=500
46 Correct 37 ms 43616 KB n=500
47 Correct 35 ms 43632 KB n=500
48 Correct 34 ms 43632 KB n=500
49 Correct 36 ms 43676 KB n=500
50 Correct 38 ms 43676 KB n=500
51 Correct 36 ms 43688 KB n=500
52 Correct 37 ms 43704 KB n=500
53 Correct 36 ms 43760 KB n=500
54 Correct 38 ms 43760 KB n=500
55 Correct 35 ms 43760 KB n=278
56 Correct 37 ms 43788 KB n=500
57 Correct 39 ms 43804 KB n=500
58 Correct 35 ms 43804 KB n=500
59 Correct 41 ms 44212 KB n=2000
60 Correct 40 ms 44264 KB n=2000
61 Correct 38 ms 44320 KB n=2000
62 Correct 41 ms 44320 KB n=2000
63 Correct 41 ms 44324 KB n=2000
64 Correct 39 ms 44404 KB n=2000
65 Correct 39 ms 44412 KB n=2000
66 Correct 41 ms 44592 KB n=2000
67 Correct 42 ms 44592 KB n=2000
68 Correct 40 ms 44828 KB n=2000
69 Correct 42 ms 44828 KB n=2000
70 Correct 40 ms 44828 KB n=2000
71 Correct 37 ms 44828 KB n=2000
72 Correct 37 ms 44876 KB n=2000
73 Correct 39 ms 44876 KB n=2000
74 Correct 43 ms 45072 KB n=1844
75 Correct 40 ms 45072 KB n=2000
76 Correct 41 ms 45072 KB n=2000
77 Correct 40 ms 45072 KB n=2000
78 Correct 40 ms 45108 KB n=2000
79 Correct 42 ms 45160 KB n=2000
80 Correct 37 ms 45432 KB n=2000
81 Correct 41 ms 45432 KB n=2000
82 Correct 37 ms 45432 KB n=2000
83 Correct 39 ms 45496 KB n=2000
84 Correct 39 ms 45496 KB n=2000
85 Correct 44 ms 45640 KB n=2000
86 Correct 38 ms 45640 KB n=2000
87 Correct 39 ms 45692 KB n=2000
88 Correct 37 ms 45784 KB n=2000
89 Correct 38 ms 45840 KB n=2000
90 Correct 47 ms 45896 KB n=2000
91 Correct 37 ms 45896 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 42620 KB n=5
2 Correct 36 ms 42720 KB n=100
3 Correct 35 ms 42760 KB n=100
4 Correct 35 ms 42764 KB n=100
5 Correct 34 ms 42896 KB n=100
6 Correct 34 ms 42896 KB n=100
7 Correct 36 ms 42984 KB n=100
8 Correct 35 ms 43096 KB n=100
9 Correct 36 ms 43096 KB n=100
10 Correct 35 ms 43100 KB n=100
11 Correct 35 ms 43128 KB n=100
12 Correct 43 ms 43128 KB n=100
13 Correct 36 ms 43128 KB n=100
14 Correct 34 ms 43128 KB n=100
15 Correct 38 ms 43128 KB n=100
16 Correct 37 ms 43148 KB n=100
17 Correct 37 ms 43148 KB n=100
18 Correct 37 ms 43148 KB n=100
19 Correct 35 ms 43148 KB n=100
20 Correct 37 ms 43148 KB n=100
21 Correct 39 ms 43168 KB n=100
22 Correct 36 ms 43168 KB n=100
23 Correct 36 ms 43168 KB n=100
24 Correct 36 ms 43168 KB n=100
25 Correct 34 ms 43168 KB n=100
26 Correct 39 ms 43168 KB n=12
27 Correct 37 ms 43168 KB n=100
28 Correct 37 ms 43168 KB n=500
29 Correct 36 ms 43208 KB n=500
30 Correct 38 ms 43240 KB n=500
31 Correct 38 ms 43272 KB n=500
32 Correct 37 ms 43272 KB n=500
33 Correct 38 ms 43276 KB n=500
34 Correct 37 ms 43296 KB n=500
35 Correct 35 ms 43432 KB n=500
36 Correct 36 ms 43432 KB n=500
37 Correct 37 ms 43460 KB n=500
38 Correct 36 ms 43460 KB n=500
39 Correct 34 ms 43500 KB n=500
40 Correct 35 ms 43500 KB n=500
41 Correct 36 ms 43500 KB n=500
42 Correct 34 ms 43500 KB n=500
43 Correct 35 ms 43500 KB n=500
44 Correct 37 ms 43500 KB n=500
45 Correct 37 ms 43604 KB n=500
46 Correct 37 ms 43616 KB n=500
47 Correct 35 ms 43632 KB n=500
48 Correct 34 ms 43632 KB n=500
49 Correct 36 ms 43676 KB n=500
50 Correct 38 ms 43676 KB n=500
51 Correct 36 ms 43688 KB n=500
52 Correct 37 ms 43704 KB n=500
53 Correct 36 ms 43760 KB n=500
54 Correct 38 ms 43760 KB n=500
55 Correct 35 ms 43760 KB n=278
56 Correct 37 ms 43788 KB n=500
57 Correct 39 ms 43804 KB n=500
58 Correct 35 ms 43804 KB n=500
59 Correct 41 ms 44212 KB n=2000
60 Correct 40 ms 44264 KB n=2000
61 Correct 38 ms 44320 KB n=2000
62 Correct 41 ms 44320 KB n=2000
63 Correct 41 ms 44324 KB n=2000
64 Correct 39 ms 44404 KB n=2000
65 Correct 39 ms 44412 KB n=2000
66 Correct 41 ms 44592 KB n=2000
67 Correct 42 ms 44592 KB n=2000
68 Correct 40 ms 44828 KB n=2000
69 Correct 42 ms 44828 KB n=2000
70 Correct 40 ms 44828 KB n=2000
71 Correct 37 ms 44828 KB n=2000
72 Correct 37 ms 44876 KB n=2000
73 Correct 39 ms 44876 KB n=2000
74 Correct 43 ms 45072 KB n=1844
75 Correct 40 ms 45072 KB n=2000
76 Correct 41 ms 45072 KB n=2000
77 Correct 40 ms 45072 KB n=2000
78 Correct 40 ms 45108 KB n=2000
79 Correct 42 ms 45160 KB n=2000
80 Correct 37 ms 45432 KB n=2000
81 Correct 41 ms 45432 KB n=2000
82 Correct 37 ms 45432 KB n=2000
83 Correct 39 ms 45496 KB n=2000
84 Correct 39 ms 45496 KB n=2000
85 Correct 44 ms 45640 KB n=2000
86 Correct 38 ms 45640 KB n=2000
87 Correct 39 ms 45692 KB n=2000
88 Correct 37 ms 45784 KB n=2000
89 Correct 38 ms 45840 KB n=2000
90 Correct 47 ms 45896 KB n=2000
91 Correct 37 ms 45896 KB n=2000
92 Correct 915 ms 95412 KB n=200000
93 Correct 1431 ms 108552 KB n=200000
94 Correct 1426 ms 120580 KB n=200000
95 Correct 944 ms 120580 KB n=200000
96 Correct 894 ms 123736 KB n=200000
97 Correct 1545 ms 135668 KB n=200000
98 Correct 939 ms 137896 KB n=200000
99 Correct 1242 ms 144568 KB n=200000
100 Correct 929 ms 151504 KB n=200000
101 Correct 1400 ms 170648 KB n=200000
102 Correct 577 ms 170648 KB n=200000
103 Correct 562 ms 173496 KB n=200000
104 Correct 557 ms 180212 KB n=200000
105 Correct 551 ms 187256 KB n=200000
106 Correct 546 ms 194656 KB n=200000
107 Correct 551 ms 201884 KB n=200000
108 Correct 1079 ms 207976 KB n=200000
109 Correct 1059 ms 214728 KB n=200000
110 Correct 1130 ms 221532 KB n=200000
111 Correct 963 ms 227832 KB n=200000
112 Correct 1512 ms 245980 KB n=200000
113 Correct 1549 ms 247516 KB n=200000
114 Correct 1006 ms 249532 KB n=200000
115 Correct 1688 ms 258536 KB n=200000
116 Correct 889 ms 262144 KB n=200000
117 Correct 1434 ms 262144 KB n=200000
118 Correct 1542 ms 262144 KB n=200000
119 Correct 931 ms 262144 KB n=200000
120 Correct 1339 ms 262144 KB n=200000
121 Correct 1375 ms 262144 KB n=200000
122 Correct 1361 ms 262144 KB n=200000
123 Correct 578 ms 262144 KB n=200000
124 Correct 250 ms 262144 KB n=25264