oj.uz

Submission #869940

# Submission time Handle Problem Language Result Execution time Memory
869940 2023-11-06T11:45:21 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
100 / 100
 804 ms 99384 KB 
#include <bits/stdc++.h>

#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define pb emplace_back
#define elif else if
#define uns unsigned
#define emp empty()
#define nll nullptr
#define S second
#define F first

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef vector < ll > vll;
typedef vector < int > vi;
typedef pair < ll, ll > pll;
typedef pair < int, int > pi;
typedef pair < ldb, ldb > pldb;
typedef vector < pair < ll, ll > > vpll;
typedef vector < pair < int, int > > vpi;

const int N = 3e5 + 11;
const int M = 1e4 + 123;
const int mod = 1e9 + 7;
const int mxlg = 19;
const int K = 20;
const int P = 31;
const ll inf = 1e9 + 10;

//mt19937 rnd(07062006);

int n, m, q;
int a[N], d[N];
int up[N][K];

set < int > s1[N], s2[N];

vector < int > g[N];

void dfs(int v = 1, int p = 0){
	up[v][0] = p;
	for(int i = 1; i < mxlg; i++) up[v][i] = up[up[v][i - 1]][i - 1];
	for(auto to : g[v])
		if(to != p)
			d[to] = d[v] + 1,
			dfs(to, v);
}

int lca(int a, int b) {
	if(d[a] < d[b]) swap(a, b);
	int k = d[a] - d[b];
	for(int i = 0; i < mxlg; i++) 
		if(((k >> i) & 1)) 
			a = up[a][i];
	if(a == b) return a;
	for(int i = mxlg - 1; i >= 0; i--) 
		if(up[a][i] != up[b][i])
			a = up[a][i], b = up[b][i];
	return up[a][0];
}

void output(){
	cin >> n >> m >> q;
	for(int u, v, i = 1; i < n; i++){
		cin >> u >> v;
		g[u].pb(v), g[v].pb(u);
	}
	dfs();
	for(int i = 1; i <= m; i++) cin >> a[i];
	for(int i = 1; i <= m; i++){
		s1[a[i]].insert(i);
		if(i != m) s2[lca(a[i], a[i + 1])].insert(i);
//		cout << lca(a[i], a[i + 1]) << ' ';
	}
	while(q--){
		int tp;
		cin >> tp;
		if(tp == 1){
			int k, x;
			cin >> k >> x;
			s1[a[k]].erase(k);
			if(k != 1) s2[lca(a[k - 1], a[k])].erase(k - 1);
			if(k != n) s2[lca(a[k], a[k + 1])].erase(k);
			a[k] = x;
			s1[a[k]].insert(k);
			if(k != 1) s2[lca(a[k - 1], a[k])].insert(k - 1);
			if(k != n) s2[lca(a[k], a[k + 1])].insert(k);
		}
		else{
			int l, r, v;
			cin >> l >> r >> v;
			auto it1 = s1[v].lower_bound(l);
			auto it2 = s2[v].lower_bound(l);
			if(it1 != s1[v].end() && *it1 <= r) cout << *it1 << ' ' << *it1 << '\n';
			else if(it2 != s2[v].end() && *it2 < r) cout << *it2 << ' ' << *it2 + 1 << '\n';
			else cout << "-1 -1\n";
		}
	}
}

const bool cases = 0;

signed main(){
//  file("disrupt");
    adiyer();
    int tt = 1;
    if(cases) cin >> tt;
    for(int i = 1; i <= tt; i++){
//      cout << "Case " << i << ":\n";
        output();
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37468 KB n=5
2 Correct 7 ms 37568 KB n=100
3 Correct 8 ms 37600 KB n=100
4 Correct 7 ms 37468 KB n=100
5 Correct 8 ms 37464 KB n=100
6 Correct 9 ms 37468 KB n=100
7 Correct 8 ms 37468 KB n=100
8 Correct 7 ms 37720 KB n=100
9 Correct 7 ms 37464 KB n=100
10 Correct 8 ms 37464 KB n=100
11 Correct 8 ms 37568 KB n=100
12 Correct 8 ms 37468 KB n=100
13 Correct 8 ms 37468 KB n=100
14 Correct 8 ms 37468 KB n=100
15 Correct 9 ms 37468 KB n=100
16 Correct 8 ms 37464 KB n=100
17 Correct 7 ms 37464 KB n=100
18 Correct 8 ms 37468 KB n=100
19 Correct 7 ms 37596 KB n=100
20 Correct 8 ms 37468 KB n=100
21 Correct 8 ms 37468 KB n=100
22 Correct 9 ms 37464 KB n=100
23 Correct 8 ms 37468 KB n=100
24 Correct 7 ms 37468 KB n=100
25 Correct 8 ms 37468 KB n=100
26 Correct 8 ms 37468 KB n=12
27 Correct 8 ms 37468 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37468 KB n=5
2 Correct 7 ms 37568 KB n=100
3 Correct 8 ms 37600 KB n=100
4 Correct 7 ms 37468 KB n=100
5 Correct 8 ms 37464 KB n=100
6 Correct 9 ms 37468 KB n=100
7 Correct 8 ms 37468 KB n=100
8 Correct 7 ms 37720 KB n=100
9 Correct 7 ms 37464 KB n=100
10 Correct 8 ms 37464 KB n=100
11 Correct 8 ms 37568 KB n=100
12 Correct 8 ms 37468 KB n=100
13 Correct 8 ms 37468 KB n=100
14 Correct 8 ms 37468 KB n=100
15 Correct 9 ms 37468 KB n=100
16 Correct 8 ms 37464 KB n=100
17 Correct 7 ms 37464 KB n=100
18 Correct 8 ms 37468 KB n=100
19 Correct 7 ms 37596 KB n=100
20 Correct 8 ms 37468 KB n=100
21 Correct 8 ms 37468 KB n=100
22 Correct 9 ms 37464 KB n=100
23 Correct 8 ms 37468 KB n=100
24 Correct 7 ms 37468 KB n=100
25 Correct 8 ms 37468 KB n=100
26 Correct 8 ms 37468 KB n=12
27 Correct 8 ms 37468 KB n=100
28 Correct 8 ms 37664 KB n=500
29 Correct 9 ms 37468 KB n=500
30 Correct 10 ms 37720 KB n=500
31 Correct 8 ms 37720 KB n=500
32 Correct 8 ms 37468 KB n=500
33 Correct 8 ms 37464 KB n=500
34 Correct 8 ms 37464 KB n=500
35 Correct 9 ms 37468 KB n=500
36 Correct 9 ms 37464 KB n=500
37 Correct 8 ms 37464 KB n=500
38 Correct 10 ms 37976 KB n=500
39 Correct 8 ms 37468 KB n=500
40 Correct 8 ms 37468 KB n=500
41 Correct 8 ms 37464 KB n=500
42 Correct 8 ms 37468 KB n=500
43 Correct 9 ms 37464 KB n=500
44 Correct 8 ms 37584 KB n=500
45 Correct 8 ms 37468 KB n=500
46 Correct 8 ms 37468 KB n=500
47 Correct 8 ms 37468 KB n=500
48 Correct 8 ms 37464 KB n=500
49 Correct 8 ms 37464 KB n=500
50 Correct 8 ms 37464 KB n=500
51 Correct 8 ms 37468 KB n=500
52 Correct 8 ms 37464 KB n=500
53 Correct 8 ms 37468 KB n=500
54 Correct 8 ms 37468 KB n=500
55 Correct 9 ms 38080 KB n=278
56 Correct 8 ms 37468 KB n=500
57 Correct 8 ms 37732 KB n=500
58 Correct 8 ms 37468 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37468 KB n=5
2 Correct 7 ms 37568 KB n=100
3 Correct 8 ms 37600 KB n=100
4 Correct 7 ms 37468 KB n=100
5 Correct 8 ms 37464 KB n=100
6 Correct 9 ms 37468 KB n=100
7 Correct 8 ms 37468 KB n=100
8 Correct 7 ms 37720 KB n=100
9 Correct 7 ms 37464 KB n=100
10 Correct 8 ms 37464 KB n=100
11 Correct 8 ms 37568 KB n=100
12 Correct 8 ms 37468 KB n=100
13 Correct 8 ms 37468 KB n=100
14 Correct 8 ms 37468 KB n=100
15 Correct 9 ms 37468 KB n=100
16 Correct 8 ms 37464 KB n=100
17 Correct 7 ms 37464 KB n=100
18 Correct 8 ms 37468 KB n=100
19 Correct 7 ms 37596 KB n=100
20 Correct 8 ms 37468 KB n=100
21 Correct 8 ms 37468 KB n=100
22 Correct 9 ms 37464 KB n=100
23 Correct 8 ms 37468 KB n=100
24 Correct 7 ms 37468 KB n=100
25 Correct 8 ms 37468 KB n=100
26 Correct 8 ms 37468 KB n=12
27 Correct 8 ms 37468 KB n=100
28 Correct 8 ms 37664 KB n=500
29 Correct 9 ms 37468 KB n=500
30 Correct 10 ms 37720 KB n=500
31 Correct 8 ms 37720 KB n=500
32 Correct 8 ms 37468 KB n=500
33 Correct 8 ms 37464 KB n=500
34 Correct 8 ms 37464 KB n=500
35 Correct 9 ms 37468 KB n=500
36 Correct 9 ms 37464 KB n=500
37 Correct 8 ms 37464 KB n=500
38 Correct 10 ms 37976 KB n=500
39 Correct 8 ms 37468 KB n=500
40 Correct 8 ms 37468 KB n=500
41 Correct 8 ms 37464 KB n=500
42 Correct 8 ms 37468 KB n=500
43 Correct 9 ms 37464 KB n=500
44 Correct 8 ms 37584 KB n=500
45 Correct 8 ms 37468 KB n=500
46 Correct 8 ms 37468 KB n=500
47 Correct 8 ms 37468 KB n=500
48 Correct 8 ms 37464 KB n=500
49 Correct 8 ms 37464 KB n=500
50 Correct 8 ms 37464 KB n=500
51 Correct 8 ms 37468 KB n=500
52 Correct 8 ms 37464 KB n=500
53 Correct 8 ms 37468 KB n=500
54 Correct 8 ms 37468 KB n=500
55 Correct 9 ms 38080 KB n=278
56 Correct 8 ms 37468 KB n=500
57 Correct 8 ms 37732 KB n=500
58 Correct 8 ms 37468 KB n=500
59 Correct 10 ms 37720 KB n=2000
60 Correct 9 ms 38536 KB n=2000
61 Correct 10 ms 37980 KB n=2000
62 Correct 12 ms 37724 KB n=2000
63 Correct 12 ms 37720 KB n=2000
64 Correct 11 ms 37724 KB n=2000
65 Correct 10 ms 37720 KB n=2000
66 Correct 10 ms 37976 KB n=2000
67 Correct 10 ms 37912 KB n=2000
68 Correct 10 ms 37764 KB n=2000
69 Correct 9 ms 37724 KB n=2000
70 Correct 10 ms 37724 KB n=2000
71 Correct 10 ms 37724 KB n=2000
72 Correct 9 ms 37724 KB n=2000
73 Correct 10 ms 37720 KB n=2000
74 Correct 10 ms 37704 KB n=1844
75 Correct 11 ms 37724 KB n=2000
76 Correct 10 ms 37724 KB n=2000
77 Correct 11 ms 37976 KB n=2000
78 Correct 10 ms 37724 KB n=2000
79 Correct 10 ms 37724 KB n=2000
80 Correct 9 ms 37976 KB n=2000
81 Correct 10 ms 37724 KB n=2000
82 Correct 11 ms 37720 KB n=2000
83 Correct 11 ms 37980 KB n=2000
84 Correct 10 ms 37720 KB n=2000
85 Correct 11 ms 37976 KB n=2000
86 Correct 10 ms 37724 KB n=2000
87 Correct 10 ms 37916 KB n=2000
88 Correct 10 ms 37976 KB n=2000
89 Correct 9 ms 37976 KB n=2000
90 Correct 10 ms 38152 KB n=2000
91 Correct 10 ms 37724 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 37468 KB n=5
2 Correct 7 ms 37568 KB n=100
3 Correct 8 ms 37600 KB n=100
4 Correct 7 ms 37468 KB n=100
5 Correct 8 ms 37464 KB n=100
6 Correct 9 ms 37468 KB n=100
7 Correct 8 ms 37468 KB n=100
8 Correct 7 ms 37720 KB n=100
9 Correct 7 ms 37464 KB n=100
10 Correct 8 ms 37464 KB n=100
11 Correct 8 ms 37568 KB n=100
12 Correct 8 ms 37468 KB n=100
13 Correct 8 ms 37468 KB n=100
14 Correct 8 ms 37468 KB n=100
15 Correct 9 ms 37468 KB n=100
16 Correct 8 ms 37464 KB n=100
17 Correct 7 ms 37464 KB n=100
18 Correct 8 ms 37468 KB n=100
19 Correct 7 ms 37596 KB n=100
20 Correct 8 ms 37468 KB n=100
21 Correct 8 ms 37468 KB n=100
22 Correct 9 ms 37464 KB n=100
23 Correct 8 ms 37468 KB n=100
24 Correct 7 ms 37468 KB n=100
25 Correct 8 ms 37468 KB n=100
26 Correct 8 ms 37468 KB n=12
27 Correct 8 ms 37468 KB n=100
28 Correct 8 ms 37664 KB n=500
29 Correct 9 ms 37468 KB n=500
30 Correct 10 ms 37720 KB n=500
31 Correct 8 ms 37720 KB n=500
32 Correct 8 ms 37468 KB n=500
33 Correct 8 ms 37464 KB n=500
34 Correct 8 ms 37464 KB n=500
35 Correct 9 ms 37468 KB n=500
36 Correct 9 ms 37464 KB n=500
37 Correct 8 ms 37464 KB n=500
38 Correct 10 ms 37976 KB n=500
39 Correct 8 ms 37468 KB n=500
40 Correct 8 ms 37468 KB n=500
41 Correct 8 ms 37464 KB n=500
42 Correct 8 ms 37468 KB n=500
43 Correct 9 ms 37464 KB n=500
44 Correct 8 ms 37584 KB n=500
45 Correct 8 ms 37468 KB n=500
46 Correct 8 ms 37468 KB n=500
47 Correct 8 ms 37468 KB n=500
48 Correct 8 ms 37464 KB n=500
49 Correct 8 ms 37464 KB n=500
50 Correct 8 ms 37464 KB n=500
51 Correct 8 ms 37468 KB n=500
52 Correct 8 ms 37464 KB n=500
53 Correct 8 ms 37468 KB n=500
54 Correct 8 ms 37468 KB n=500
55 Correct 9 ms 38080 KB n=278
56 Correct 8 ms 37468 KB n=500
57 Correct 8 ms 37732 KB n=500
58 Correct 8 ms 37468 KB n=500
59 Correct 10 ms 37720 KB n=2000
60 Correct 9 ms 38536 KB n=2000
61 Correct 10 ms 37980 KB n=2000
62 Correct 12 ms 37724 KB n=2000
63 Correct 12 ms 37720 KB n=2000
64 Correct 11 ms 37724 KB n=2000
65 Correct 10 ms 37720 KB n=2000
66 Correct 10 ms 37976 KB n=2000
67 Correct 10 ms 37912 KB n=2000
68 Correct 10 ms 37764 KB n=2000
69 Correct 9 ms 37724 KB n=2000
70 Correct 10 ms 37724 KB n=2000
71 Correct 10 ms 37724 KB n=2000
72 Correct 9 ms 37724 KB n=2000
73 Correct 10 ms 37720 KB n=2000
74 Correct 10 ms 37704 KB n=1844
75 Correct 11 ms 37724 KB n=2000
76 Correct 10 ms 37724 KB n=2000
77 Correct 11 ms 37976 KB n=2000
78 Correct 10 ms 37724 KB n=2000
79 Correct 10 ms 37724 KB n=2000
80 Correct 9 ms 37976 KB n=2000
81 Correct 10 ms 37724 KB n=2000
82 Correct 11 ms 37720 KB n=2000
83 Correct 11 ms 37980 KB n=2000
84 Correct 10 ms 37720 KB n=2000
85 Correct 11 ms 37976 KB n=2000
86 Correct 10 ms 37724 KB n=2000
87 Correct 10 ms 37916 KB n=2000
88 Correct 10 ms 37976 KB n=2000
89 Correct 9 ms 37976 KB n=2000
90 Correct 10 ms 38152 KB n=2000
91 Correct 10 ms 37724 KB n=2000
92 Correct 552 ms 86888 KB n=200000
93 Correct 729 ms 93264 KB n=200000
94 Correct 725 ms 97908 KB n=200000
95 Correct 577 ms 86800 KB n=200000
96 Correct 542 ms 86824 KB n=200000
97 Correct 804 ms 92224 KB n=200000
98 Correct 507 ms 86728 KB n=200000
99 Correct 686 ms 87228 KB n=200000
100 Correct 537 ms 86732 KB n=200000
101 Correct 746 ms 99384 KB n=200000
102 Correct 332 ms 88216 KB n=200000
103 Correct 319 ms 88040 KB n=200000
104 Correct 312 ms 87888 KB n=200000
105 Correct 335 ms 88404 KB n=200000
106 Correct 324 ms 88400 KB n=200000
107 Correct 348 ms 88332 KB n=200000
108 Correct 607 ms 86864 KB n=200000
109 Correct 657 ms 86868 KB n=200000
110 Correct 588 ms 86868 KB n=200000
111 Correct 531 ms 86348 KB n=200000
112 Correct 748 ms 98452 KB n=200000
113 Correct 739 ms 92096 KB n=200000
114 Correct 533 ms 86292 KB n=200000
115 Correct 751 ms 89200 KB n=200000
116 Correct 498 ms 86908 KB n=200000
117 Correct 717 ms 98928 KB n=200000
118 Correct 696 ms 90604 KB n=200000
119 Correct 506 ms 87108 KB n=200000
120 Correct 710 ms 99008 KB n=200000
121 Correct 690 ms 98696 KB n=200000
122 Correct 653 ms 98932 KB n=200000
123 Correct 331 ms 88372 KB n=200000
124 Correct 136 ms 52920 KB n=25264