oj.uz

Submission #643087

# Submission time Handle Problem Language Result Execution time Memory
643087 2022-09-21T07:38:52 Z ghostwriter Birthday gift (IZhO18_treearray) C++14
100 / 100
 938 ms 82340 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    CTL - Da Lat
    Cay ngay cay dem nhung deo duoc cong nhan
*/
const int N = 2e5 + 5;
int n, m, q, a[N], h[N], p[N][18];
vi adj[N];
multiset<int> s[N], s1[N];
void dfs(int u, int p) {
	::p[u][0] = p;
	h[u] = h[p] + 1;
	EACH(v, adj[u]) {
		if (v == p) continue;
		dfs(v, u);
	}
}
void build() {
	FOR(j, 1, 17)
	FOR(i, 1, n)
		p[i][j] = p[p[i][j - 1]][j - 1];
}
int lca(int a, int b) {
	if (h[a] > h[b]) swap(a, b);
	int diff = h[b] - h[a];
	FOR(i, 0, 17)
		if (diff & (1 << i)) b = p[b][i];
	if (a == b) return a;
	FOS(i, 17, 0)
		if (p[a][i] != p[b][i]) {
			a = p[a][i];
			b = p[b][i];
		}
	return p[a][0];
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n >> m >> q;
    FOR(i, 1, n - 1) {
    	int u, v;
    	cin >> u >> v;
    	adj[u].pb(v);
    	adj[v].pb(u);
    }
    FOR(i, 1, m) cin >> a[i];
    dfs(1, 0);
    build();
    a[m + 1] = 1;
    FOR(i, 1, m) {
    	s[a[i]].insert(i);
    	s1[lca(a[i], a[i + 1])].insert(i);
    }
    WHILE(q--) {
    	int t;
    	cin >> t;
    	if (t == 2) {
    		int l, r, v;
    		cin >> l >> r >> v;
    		if (!s[v].empty() && *--s[v].end() >= l) {
    			int pos = *s[v].lb(l);
    			if (pos <= r) {
    				cout << pos << ' ' << pos << '\n';
    				continue;
    			}
    		}
    		if (!s1[v].empty() && *--s1[v].end() >= l) {
    			int pos = *s1[v].lb(l);
    			if (pos + 1 <= r) {
    				cout << pos << ' ' << pos + 1 << '\n';
    				continue;
    			}
    		}
    		cout << -1 << ' ' << -1 << '\n';
    		continue;
    	}
    	int pos, v;
    	cin >> pos >> v;
    	s[a[pos]].erase(pos);
    	if (pos > 1) s1[lca(a[pos - 1], a[pos])].erase(pos - 1);
    	s1[lca(a[pos], a[pos + 1])].erase(pos);
    	a[pos] = v;
    	s[a[pos]].insert(pos);
    	if (pos > 1) s1[lca(a[pos - 1], a[pos])].insert(pos - 1);
    	s1[lca(a[pos], a[pos + 1])].insert(pos);
    }
    return 0;
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5 
2 3 4 5
2 1 3 1
*/

Compilation message

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:26:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   26 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
treearray.cpp:43:2: note: in expansion of macro 'EACH'
   43 |  EACH(v, adj[u]) {
      |  ^~~~
treearray.cpp: In function 'void build()':
treearray.cpp:24:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
treearray.cpp:49:2: note: in expansion of macro 'FOR'
   49 |  FOR(j, 1, 17)
      |  ^~~
treearray.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
treearray.cpp:50:2: note: in expansion of macro 'FOR'
   50 |  FOR(i, 1, n)
      |  ^~~
treearray.cpp: In function 'int lca(int, int)':
treearray.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
treearray.cpp:56:2: note: in expansion of macro 'FOR'
   56 |  FOR(i, 0, 17)
      |  ^~~
treearray.cpp:25:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   25 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
treearray.cpp:59:2: note: in expansion of macro 'FOS'
   59 |  FOS(i, 17, 0)
      |  ^~~
treearray.cpp: In function 'int main()':
treearray.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
treearray.cpp:71:5: note: in expansion of macro 'FOR'
   71 |     FOR(i, 1, n - 1) {
      |     ^~~
treearray.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
treearray.cpp:77:5: note: in expansion of macro 'FOR'
   77 |     FOR(i, 1, m) cin >> a[i];
      |     ^~~
treearray.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
treearray.cpp:81:5: note: in expansion of macro 'FOR'
   81 |     FOR(i, 1, m) {
      |     ^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB n=5
2 Correct 13 ms 23760 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 12 ms 23812 KB n=100
6 Correct 14 ms 23796 KB n=100
7 Correct 12 ms 23764 KB n=100
8 Correct 14 ms 23764 KB n=100
9 Correct 13 ms 23764 KB n=100
10 Correct 12 ms 23840 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 12 ms 23820 KB n=100
13 Correct 12 ms 23824 KB n=100
14 Correct 12 ms 23764 KB n=100
15 Correct 12 ms 23816 KB n=100
16 Correct 12 ms 23764 KB n=100
17 Correct 12 ms 23812 KB n=100
18 Correct 12 ms 23764 KB n=100
19 Correct 12 ms 23764 KB n=100
20 Correct 13 ms 23744 KB n=100
21 Correct 12 ms 23828 KB n=100
22 Correct 14 ms 23812 KB n=100
23 Correct 12 ms 23764 KB n=100
24 Correct 13 ms 23816 KB n=100
25 Correct 15 ms 23776 KB n=100
26 Correct 12 ms 23764 KB n=12
27 Correct 13 ms 23764 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB n=5
2 Correct 13 ms 23760 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 12 ms 23812 KB n=100
6 Correct 14 ms 23796 KB n=100
7 Correct 12 ms 23764 KB n=100
8 Correct 14 ms 23764 KB n=100
9 Correct 13 ms 23764 KB n=100
10 Correct 12 ms 23840 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 12 ms 23820 KB n=100
13 Correct 12 ms 23824 KB n=100
14 Correct 12 ms 23764 KB n=100
15 Correct 12 ms 23816 KB n=100
16 Correct 12 ms 23764 KB n=100
17 Correct 12 ms 23812 KB n=100
18 Correct 12 ms 23764 KB n=100
19 Correct 12 ms 23764 KB n=100
20 Correct 13 ms 23744 KB n=100
21 Correct 12 ms 23828 KB n=100
22 Correct 14 ms 23812 KB n=100
23 Correct 12 ms 23764 KB n=100
24 Correct 13 ms 23816 KB n=100
25 Correct 15 ms 23776 KB n=100
26 Correct 12 ms 23764 KB n=12
27 Correct 13 ms 23764 KB n=100
28 Correct 12 ms 23892 KB n=500
29 Correct 12 ms 23888 KB n=500
30 Correct 12 ms 23892 KB n=500
31 Correct 15 ms 23860 KB n=500
32 Correct 13 ms 23932 KB n=500
33 Correct 14 ms 24020 KB n=500
34 Correct 12 ms 23928 KB n=500
35 Correct 13 ms 23892 KB n=500
36 Correct 13 ms 23948 KB n=500
37 Correct 13 ms 23892 KB n=500
38 Correct 13 ms 23896 KB n=500
39 Correct 12 ms 23892 KB n=500
40 Correct 12 ms 23892 KB n=500
41 Correct 13 ms 23880 KB n=500
42 Correct 13 ms 23892 KB n=500
43 Correct 13 ms 23892 KB n=500
44 Correct 13 ms 23892 KB n=500
45 Correct 12 ms 23948 KB n=500
46 Correct 13 ms 23904 KB n=500
47 Correct 14 ms 23956 KB n=500
48 Correct 13 ms 23868 KB n=500
49 Correct 12 ms 23892 KB n=500
50 Correct 13 ms 23892 KB n=500
51 Correct 14 ms 24020 KB n=500
52 Correct 13 ms 23960 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 13 ms 23892 KB n=500
55 Correct 12 ms 23820 KB n=278
56 Correct 13 ms 23896 KB n=500
57 Correct 13 ms 23892 KB n=500
58 Correct 13 ms 23928 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB n=5
2 Correct 13 ms 23760 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 12 ms 23812 KB n=100
6 Correct 14 ms 23796 KB n=100
7 Correct 12 ms 23764 KB n=100
8 Correct 14 ms 23764 KB n=100
9 Correct 13 ms 23764 KB n=100
10 Correct 12 ms 23840 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 12 ms 23820 KB n=100
13 Correct 12 ms 23824 KB n=100
14 Correct 12 ms 23764 KB n=100
15 Correct 12 ms 23816 KB n=100
16 Correct 12 ms 23764 KB n=100
17 Correct 12 ms 23812 KB n=100
18 Correct 12 ms 23764 KB n=100
19 Correct 12 ms 23764 KB n=100
20 Correct 13 ms 23744 KB n=100
21 Correct 12 ms 23828 KB n=100
22 Correct 14 ms 23812 KB n=100
23 Correct 12 ms 23764 KB n=100
24 Correct 13 ms 23816 KB n=100
25 Correct 15 ms 23776 KB n=100
26 Correct 12 ms 23764 KB n=12
27 Correct 13 ms 23764 KB n=100
28 Correct 12 ms 23892 KB n=500
29 Correct 12 ms 23888 KB n=500
30 Correct 12 ms 23892 KB n=500
31 Correct 15 ms 23860 KB n=500
32 Correct 13 ms 23932 KB n=500
33 Correct 14 ms 24020 KB n=500
34 Correct 12 ms 23928 KB n=500
35 Correct 13 ms 23892 KB n=500
36 Correct 13 ms 23948 KB n=500
37 Correct 13 ms 23892 KB n=500
38 Correct 13 ms 23896 KB n=500
39 Correct 12 ms 23892 KB n=500
40 Correct 12 ms 23892 KB n=500
41 Correct 13 ms 23880 KB n=500
42 Correct 13 ms 23892 KB n=500
43 Correct 13 ms 23892 KB n=500
44 Correct 13 ms 23892 KB n=500
45 Correct 12 ms 23948 KB n=500
46 Correct 13 ms 23904 KB n=500
47 Correct 14 ms 23956 KB n=500
48 Correct 13 ms 23868 KB n=500
49 Correct 12 ms 23892 KB n=500
50 Correct 13 ms 23892 KB n=500
51 Correct 14 ms 24020 KB n=500
52 Correct 13 ms 23960 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 13 ms 23892 KB n=500
55 Correct 12 ms 23820 KB n=278
56 Correct 13 ms 23896 KB n=500
57 Correct 13 ms 23892 KB n=500
58 Correct 13 ms 23928 KB n=500
59 Correct 14 ms 24276 KB n=2000
60 Correct 17 ms 24292 KB n=2000
61 Correct 18 ms 24276 KB n=2000
62 Correct 15 ms 24320 KB n=2000
63 Correct 14 ms 24276 KB n=2000
64 Correct 14 ms 24276 KB n=2000
65 Correct 14 ms 24208 KB n=2000
66 Correct 15 ms 24276 KB n=2000
67 Correct 17 ms 24276 KB n=2000
68 Correct 15 ms 24276 KB n=2000
69 Correct 14 ms 24204 KB n=2000
70 Correct 16 ms 24236 KB n=2000
71 Correct 14 ms 24200 KB n=2000
72 Correct 14 ms 24216 KB n=2000
73 Correct 17 ms 24276 KB n=2000
74 Correct 14 ms 24252 KB n=1844
75 Correct 14 ms 24240 KB n=2000
76 Correct 15 ms 24276 KB n=2000
77 Correct 15 ms 24276 KB n=2000
78 Correct 15 ms 24220 KB n=2000
79 Correct 15 ms 24276 KB n=2000
80 Correct 15 ms 24340 KB n=2000
81 Correct 15 ms 24276 KB n=2000
82 Correct 14 ms 24276 KB n=2000
83 Correct 15 ms 24328 KB n=2000
84 Correct 15 ms 24276 KB n=2000
85 Correct 15 ms 24212 KB n=2000
86 Correct 17 ms 24324 KB n=2000
87 Correct 15 ms 24300 KB n=2000
88 Correct 15 ms 24276 KB n=2000
89 Correct 14 ms 24380 KB n=2000
90 Correct 15 ms 24340 KB n=2000
91 Correct 14 ms 24276 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB n=5
2 Correct 13 ms 23760 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 12 ms 23812 KB n=100
6 Correct 14 ms 23796 KB n=100
7 Correct 12 ms 23764 KB n=100
8 Correct 14 ms 23764 KB n=100
9 Correct 13 ms 23764 KB n=100
10 Correct 12 ms 23840 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 12 ms 23820 KB n=100
13 Correct 12 ms 23824 KB n=100
14 Correct 12 ms 23764 KB n=100
15 Correct 12 ms 23816 KB n=100
16 Correct 12 ms 23764 KB n=100
17 Correct 12 ms 23812 KB n=100
18 Correct 12 ms 23764 KB n=100
19 Correct 12 ms 23764 KB n=100
20 Correct 13 ms 23744 KB n=100
21 Correct 12 ms 23828 KB n=100
22 Correct 14 ms 23812 KB n=100
23 Correct 12 ms 23764 KB n=100
24 Correct 13 ms 23816 KB n=100
25 Correct 15 ms 23776 KB n=100
26 Correct 12 ms 23764 KB n=12
27 Correct 13 ms 23764 KB n=100
28 Correct 12 ms 23892 KB n=500
29 Correct 12 ms 23888 KB n=500
30 Correct 12 ms 23892 KB n=500
31 Correct 15 ms 23860 KB n=500
32 Correct 13 ms 23932 KB n=500
33 Correct 14 ms 24020 KB n=500
34 Correct 12 ms 23928 KB n=500
35 Correct 13 ms 23892 KB n=500
36 Correct 13 ms 23948 KB n=500
37 Correct 13 ms 23892 KB n=500
38 Correct 13 ms 23896 KB n=500
39 Correct 12 ms 23892 KB n=500
40 Correct 12 ms 23892 KB n=500
41 Correct 13 ms 23880 KB n=500
42 Correct 13 ms 23892 KB n=500
43 Correct 13 ms 23892 KB n=500
44 Correct 13 ms 23892 KB n=500
45 Correct 12 ms 23948 KB n=500
46 Correct 13 ms 23904 KB n=500
47 Correct 14 ms 23956 KB n=500
48 Correct 13 ms 23868 KB n=500
49 Correct 12 ms 23892 KB n=500
50 Correct 13 ms 23892 KB n=500
51 Correct 14 ms 24020 KB n=500
52 Correct 13 ms 23960 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 13 ms 23892 KB n=500
55 Correct 12 ms 23820 KB n=278
56 Correct 13 ms 23896 KB n=500
57 Correct 13 ms 23892 KB n=500
58 Correct 13 ms 23928 KB n=500
59 Correct 14 ms 24276 KB n=2000
60 Correct 17 ms 24292 KB n=2000
61 Correct 18 ms 24276 KB n=2000
62 Correct 15 ms 24320 KB n=2000
63 Correct 14 ms 24276 KB n=2000
64 Correct 14 ms 24276 KB n=2000
65 Correct 14 ms 24208 KB n=2000
66 Correct 15 ms 24276 KB n=2000
67 Correct 17 ms 24276 KB n=2000
68 Correct 15 ms 24276 KB n=2000
69 Correct 14 ms 24204 KB n=2000
70 Correct 16 ms 24236 KB n=2000
71 Correct 14 ms 24200 KB n=2000
72 Correct 14 ms 24216 KB n=2000
73 Correct 17 ms 24276 KB n=2000
74 Correct 14 ms 24252 KB n=1844
75 Correct 14 ms 24240 KB n=2000
76 Correct 15 ms 24276 KB n=2000
77 Correct 15 ms 24276 KB n=2000
78 Correct 15 ms 24220 KB n=2000
79 Correct 15 ms 24276 KB n=2000
80 Correct 15 ms 24340 KB n=2000
81 Correct 15 ms 24276 KB n=2000
82 Correct 14 ms 24276 KB n=2000
83 Correct 15 ms 24328 KB n=2000
84 Correct 15 ms 24276 KB n=2000
85 Correct 15 ms 24212 KB n=2000
86 Correct 17 ms 24324 KB n=2000
87 Correct 15 ms 24300 KB n=2000
88 Correct 15 ms 24276 KB n=2000
89 Correct 14 ms 24380 KB n=2000
90 Correct 15 ms 24340 KB n=2000
91 Correct 14 ms 24276 KB n=2000
92 Correct 634 ms 73084 KB n=200000
93 Correct 813 ms 77572 KB n=200000
94 Correct 783 ms 80864 KB n=200000
95 Correct 638 ms 72776 KB n=200000
96 Correct 599 ms 72876 KB n=200000
97 Correct 846 ms 76620 KB n=200000
98 Correct 667 ms 72800 KB n=200000
99 Correct 739 ms 72908 KB n=200000
100 Correct 609 ms 72904 KB n=200000
101 Correct 782 ms 82340 KB n=200000
102 Correct 394 ms 73940 KB n=200000
103 Correct 395 ms 73980 KB n=200000
104 Correct 386 ms 74004 KB n=200000
105 Correct 414 ms 74200 KB n=200000
106 Correct 397 ms 74232 KB n=200000
107 Correct 407 ms 74244 KB n=200000
108 Correct 698 ms 72936 KB n=200000
109 Correct 725 ms 72924 KB n=200000
110 Correct 695 ms 73000 KB n=200000
111 Correct 620 ms 72200 KB n=200000
112 Correct 773 ms 80780 KB n=200000
113 Correct 835 ms 76284 KB n=200000
114 Correct 618 ms 72440 KB n=200000
115 Correct 938 ms 74184 KB n=200000
116 Correct 594 ms 72900 KB n=200000
117 Correct 807 ms 81260 KB n=200000
118 Correct 855 ms 75112 KB n=200000
119 Correct 589 ms 72928 KB n=200000
120 Correct 738 ms 81512 KB n=200000
121 Correct 705 ms 81432 KB n=200000
122 Correct 711 ms 81836 KB n=200000
123 Correct 390 ms 73652 KB n=200000
124 Correct 203 ms 38516 KB n=25264