oj.uz

답안 #1100573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100573 2024-10-14T09:13:40 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
56 / 100
 26 ms 34196 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()

const int N = 100001;

using namespace std;

ll n, m, k, a, b, c, e, d[N], bg[N], p[N], sz[N], h[N], up[N][22], tin[N], lc, sum, sum1, ans, mx[N], tout[N];
set <ll> s[N], st[N];
vector <ll> g[N];

void dfs (ll v, ll pp){
	up[v][0] = pp;
	sz[v] = 1;
	for (int i = 1; i <= 21; i++){
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	for (int i = 0; i < g[v].size(); i++){
		if (g[v][i] != pp){
			d[g[v][i]] = d[v] + 1;
			dfs (g[v][i], v);
		}
	}
}

ll lca (ll a, ll b){
	if (d[a] < d[b]){
		swap (a, b);
	}
	ll c = abs (d[a] - d[b]);
	for (int i = 21; i >= 0; i--){
		if ((c >> i) & 1){
			a = up[a][i];
		}
	}
	if (a == b){
		return a;
	}
	for (int i = 21; i >= 0; i--){
		if (up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}

signed main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++){
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb (a);
	}
	for (int i = 1; i <= m; i++){
		cin >> p[i];
	}
	dfs (1, 0);
	for (int i = 1; i < m; i++){
		st[p[i]].insert (i);
		s[lca (p[i], p[i + 1])].insert (i);
	}
	st[p[m]].insert(m);
	while (k--){
		cin >> a >> b >> c;
		if (a == 1){
			st[p[b]].erase (b);
			if (b != 1)s[lca (p[b], p[b - 1])].erase (b - 1);
			if (b != m)s[lca (p[b], p[b + 1])].erase (b);
			p[b] = c;
			st[p[b]].insert(b);
			if (b != 1)s[lca (p[b], p[b - 1])].insert (b - 1);
			if (b != m)s[lca (p[b], p[b + 1])].insert (b);
		}
		else{
			cin >> e;
			if (s[e].size() && *s[e].lower_bound(b) < c && *s[e].lower_bound(b) >= b){
				lc = *s[e].lower_bound(b);
				cout << lc << ' ' << lc + 1 << '\n';
			}
			else if (st[e].size() && *st[e].lower_bound(b) <= c && *st[e].lower_bound(b) >= b){
				cout << *st[e].lower_bound(b) << ' ' << *st[e].lower_bound (b) << '\n';
			}
			else{
				cout << "-1 -1\n";
			}
		}
	}
}

Compilation message

treearray.cpp: In function 'void dfs(long long int, long long int)':
treearray.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0; i < g[v].size(); i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16976 KB n=5
2 Correct 4 ms 16976 KB n=100
3 Correct 3 ms 16976 KB n=100
4 Correct 3 ms 16976 KB n=100
5 Correct 3 ms 16976 KB n=100
6 Correct 3 ms 16976 KB n=100
7 Correct 3 ms 16976 KB n=100
8 Correct 3 ms 16976 KB n=100
9 Correct 3 ms 16976 KB n=100
10 Correct 3 ms 16976 KB n=100
11 Correct 3 ms 16976 KB n=100
12 Correct 3 ms 16976 KB n=100
13 Correct 3 ms 16976 KB n=100
14 Correct 3 ms 16976 KB n=100
15 Correct 3 ms 17144 KB n=100
16 Correct 3 ms 16976 KB n=100
17 Correct 3 ms 16976 KB n=100
18 Correct 3 ms 16976 KB n=100
19 Correct 3 ms 16976 KB n=100
20 Correct 3 ms 16988 KB n=100
21 Correct 3 ms 17132 KB n=100
22 Correct 3 ms 16976 KB n=100
23 Correct 3 ms 16976 KB n=100
24 Correct 3 ms 16976 KB n=100
25 Correct 3 ms 16988 KB n=100
26 Correct 3 ms 16976 KB n=12
27 Correct 3 ms 16976 KB n=100

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16976 KB n=5
2 Correct 4 ms 16976 KB n=100
3 Correct 3 ms 16976 KB n=100
4 Correct 3 ms 16976 KB n=100
5 Correct 3 ms 16976 KB n=100
6 Correct 3 ms 16976 KB n=100
7 Correct 3 ms 16976 KB n=100
8 Correct 3 ms 16976 KB n=100
9 Correct 3 ms 16976 KB n=100
10 Correct 3 ms 16976 KB n=100
11 Correct 3 ms 16976 KB n=100
12 Correct 3 ms 16976 KB n=100
13 Correct 3 ms 16976 KB n=100
14 Correct 3 ms 16976 KB n=100
15 Correct 3 ms 17144 KB n=100
16 Correct 3 ms 16976 KB n=100
17 Correct 3 ms 16976 KB n=100
18 Correct 3 ms 16976 KB n=100
19 Correct 3 ms 16976 KB n=100
20 Correct 3 ms 16988 KB n=100
21 Correct 3 ms 17132 KB n=100
22 Correct 3 ms 16976 KB n=100
23 Correct 3 ms 16976 KB n=100
24 Correct 3 ms 16976 KB n=100
25 Correct 3 ms 16988 KB n=100
26 Correct 3 ms 16976 KB n=12
27 Correct 3 ms 16976 KB n=100
28 Correct 4 ms 16976 KB n=500
29 Correct 4 ms 16976 KB n=500
30 Correct 3 ms 16976 KB n=500
31 Correct 3 ms 16976 KB n=500
32 Correct 3 ms 16976 KB n=500
33 Correct 3 ms 17144 KB n=500
34 Correct 3 ms 16976 KB n=500
35 Correct 4 ms 17128 KB n=500
36 Correct 4 ms 17068 KB n=500
37 Correct 3 ms 16976 KB n=500
38 Correct 3 ms 16976 KB n=500
39 Correct 3 ms 16976 KB n=500
40 Correct 3 ms 16976 KB n=500
41 Correct 3 ms 16976 KB n=500
42 Correct 4 ms 17144 KB n=500
43 Correct 3 ms 16976 KB n=500
44 Correct 3 ms 16976 KB n=500
45 Correct 4 ms 16976 KB n=500
46 Correct 4 ms 16976 KB n=500
47 Correct 3 ms 16976 KB n=500
48 Correct 4 ms 17148 KB n=500
49 Correct 3 ms 16976 KB n=500
50 Correct 3 ms 16976 KB n=500
51 Correct 4 ms 16976 KB n=500
52 Correct 4 ms 16960 KB n=500
53 Correct 4 ms 16976 KB n=500
54 Correct 4 ms 16976 KB n=500
55 Correct 4 ms 16976 KB n=278
56 Correct 4 ms 16976 KB n=500
57 Correct 4 ms 16976 KB n=500
58 Correct 4 ms 16976 KB n=500

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16976 KB n=5
2 Correct 4 ms 16976 KB n=100
3 Correct 3 ms 16976 KB n=100
4 Correct 3 ms 16976 KB n=100
5 Correct 3 ms 16976 KB n=100
6 Correct 3 ms 16976 KB n=100
7 Correct 3 ms 16976 KB n=100
8 Correct 3 ms 16976 KB n=100
9 Correct 3 ms 16976 KB n=100
10 Correct 3 ms 16976 KB n=100
11 Correct 3 ms 16976 KB n=100
12 Correct 3 ms 16976 KB n=100
13 Correct 3 ms 16976 KB n=100
14 Correct 3 ms 16976 KB n=100
15 Correct 3 ms 17144 KB n=100
16 Correct 3 ms 16976 KB n=100
17 Correct 3 ms 16976 KB n=100
18 Correct 3 ms 16976 KB n=100
19 Correct 3 ms 16976 KB n=100
20 Correct 3 ms 16988 KB n=100
21 Correct 3 ms 17132 KB n=100
22 Correct 3 ms 16976 KB n=100
23 Correct 3 ms 16976 KB n=100
24 Correct 3 ms 16976 KB n=100
25 Correct 3 ms 16988 KB n=100
26 Correct 3 ms 16976 KB n=12
27 Correct 3 ms 16976 KB n=100
28 Correct 4 ms 16976 KB n=500
29 Correct 4 ms 16976 KB n=500
30 Correct 3 ms 16976 KB n=500
31 Correct 3 ms 16976 KB n=500
32 Correct 3 ms 16976 KB n=500
33 Correct 3 ms 17144 KB n=500
34 Correct 3 ms 16976 KB n=500
35 Correct 4 ms 17128 KB n=500
36 Correct 4 ms 17068 KB n=500
37 Correct 3 ms 16976 KB n=500
38 Correct 3 ms 16976 KB n=500
39 Correct 3 ms 16976 KB n=500
40 Correct 3 ms 16976 KB n=500
41 Correct 3 ms 16976 KB n=500
42 Correct 4 ms 17144 KB n=500
43 Correct 3 ms 16976 KB n=500
44 Correct 3 ms 16976 KB n=500
45 Correct 4 ms 16976 KB n=500
46 Correct 4 ms 16976 KB n=500
47 Correct 3 ms 16976 KB n=500
48 Correct 4 ms 17148 KB n=500
49 Correct 3 ms 16976 KB n=500
50 Correct 3 ms 16976 KB n=500
51 Correct 4 ms 16976 KB n=500
52 Correct 4 ms 16960 KB n=500
53 Correct 4 ms 16976 KB n=500
54 Correct 4 ms 16976 KB n=500
55 Correct 4 ms 16976 KB n=278
56 Correct 4 ms 16976 KB n=500
57 Correct 4 ms 16976 KB n=500
58 Correct 4 ms 16976 KB n=500
59 Correct 8 ms 17232 KB n=2000
60 Correct 5 ms 17408 KB n=2000
61 Correct 5 ms 17232 KB n=2000
62 Correct 6 ms 17232 KB n=2000
63 Correct 6 ms 17400 KB n=2000
64 Correct 6 ms 17232 KB n=2000
65 Correct 6 ms 17232 KB n=2000
66 Correct 6 ms 17232 KB n=2000
67 Correct 6 ms 17232 KB n=2000
68 Correct 6 ms 17232 KB n=2000
69 Correct 5 ms 17232 KB n=2000
70 Correct 5 ms 17232 KB n=2000
71 Correct 5 ms 17232 KB n=2000
72 Correct 5 ms 17232 KB n=2000
73 Correct 6 ms 17232 KB n=2000
74 Correct 6 ms 17232 KB n=1844
75 Correct 5 ms 17232 KB n=2000
76 Correct 6 ms 17232 KB n=2000
77 Correct 6 ms 17232 KB n=2000
78 Correct 6 ms 17232 KB n=2000
79 Correct 5 ms 17232 KB n=2000
80 Correct 5 ms 17232 KB n=2000
81 Correct 6 ms 17232 KB n=2000
82 Correct 5 ms 17232 KB n=2000
83 Correct 5 ms 17400 KB n=2000
84 Correct 6 ms 17232 KB n=2000
85 Correct 6 ms 17232 KB n=2000
86 Correct 6 ms 17232 KB n=2000
87 Correct 6 ms 17232 KB n=2000
88 Correct 6 ms 17400 KB n=2000
89 Correct 5 ms 17244 KB n=2000
90 Correct 6 ms 17232 KB n=2000
91 Correct 5 ms 17232 KB n=2000

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 16976 KB n=5
2 Correct 4 ms 16976 KB n=100
3 Correct 3 ms 16976 KB n=100
4 Correct 3 ms 16976 KB n=100
5 Correct 3 ms 16976 KB n=100
6 Correct 3 ms 16976 KB n=100
7 Correct 3 ms 16976 KB n=100
8 Correct 3 ms 16976 KB n=100
9 Correct 3 ms 16976 KB n=100
10 Correct 3 ms 16976 KB n=100
11 Correct 3 ms 16976 KB n=100
12 Correct 3 ms 16976 KB n=100
13 Correct 3 ms 16976 KB n=100
14 Correct 3 ms 16976 KB n=100
15 Correct 3 ms 17144 KB n=100
16 Correct 3 ms 16976 KB n=100
17 Correct 3 ms 16976 KB n=100
18 Correct 3 ms 16976 KB n=100
19 Correct 3 ms 16976 KB n=100
20 Correct 3 ms 16988 KB n=100
21 Correct 3 ms 17132 KB n=100
22 Correct 3 ms 16976 KB n=100
23 Correct 3 ms 16976 KB n=100
24 Correct 3 ms 16976 KB n=100
25 Correct 3 ms 16988 KB n=100
26 Correct 3 ms 16976 KB n=12
27 Correct 3 ms 16976 KB n=100
28 Correct 4 ms 16976 KB n=500
29 Correct 4 ms 16976 KB n=500
30 Correct 3 ms 16976 KB n=500
31 Correct 3 ms 16976 KB n=500
32 Correct 3 ms 16976 KB n=500
33 Correct 3 ms 17144 KB n=500
34 Correct 3 ms 16976 KB n=500
35 Correct 4 ms 17128 KB n=500
36 Correct 4 ms 17068 KB n=500
37 Correct 3 ms 16976 KB n=500
38 Correct 3 ms 16976 KB n=500
39 Correct 3 ms 16976 KB n=500
40 Correct 3 ms 16976 KB n=500
41 Correct 3 ms 16976 KB n=500
42 Correct 4 ms 17144 KB n=500
43 Correct 3 ms 16976 KB n=500
44 Correct 3 ms 16976 KB n=500
45 Correct 4 ms 16976 KB n=500
46 Correct 4 ms 16976 KB n=500
47 Correct 3 ms 16976 KB n=500
48 Correct 4 ms 17148 KB n=500
49 Correct 3 ms 16976 KB n=500
50 Correct 3 ms 16976 KB n=500
51 Correct 4 ms 16976 KB n=500
52 Correct 4 ms 16960 KB n=500
53 Correct 4 ms 16976 KB n=500
54 Correct 4 ms 16976 KB n=500
55 Correct 4 ms 16976 KB n=278
56 Correct 4 ms 16976 KB n=500
57 Correct 4 ms 16976 KB n=500
58 Correct 4 ms 16976 KB n=500
59 Correct 8 ms 17232 KB n=2000
60 Correct 5 ms 17408 KB n=2000
61 Correct 5 ms 17232 KB n=2000
62 Correct 6 ms 17232 KB n=2000
63 Correct 6 ms 17400 KB n=2000
64 Correct 6 ms 17232 KB n=2000
65 Correct 6 ms 17232 KB n=2000
66 Correct 6 ms 17232 KB n=2000
67 Correct 6 ms 17232 KB n=2000
68 Correct 6 ms 17232 KB n=2000
69 Correct 5 ms 17232 KB n=2000
70 Correct 5 ms 17232 KB n=2000
71 Correct 5 ms 17232 KB n=2000
72 Correct 5 ms 17232 KB n=2000
73 Correct 6 ms 17232 KB n=2000
74 Correct 6 ms 17232 KB n=1844
75 Correct 5 ms 17232 KB n=2000
76 Correct 6 ms 17232 KB n=2000
77 Correct 6 ms 17232 KB n=2000
78 Correct 6 ms 17232 KB n=2000
79 Correct 5 ms 17232 KB n=2000
80 Correct 5 ms 17232 KB n=2000
81 Correct 6 ms 17232 KB n=2000
82 Correct 5 ms 17232 KB n=2000
83 Correct 5 ms 17400 KB n=2000
84 Correct 6 ms 17232 KB n=2000
85 Correct 6 ms 17232 KB n=2000
86 Correct 6 ms 17232 KB n=2000
87 Correct 6 ms 17232 KB n=2000
88 Correct 6 ms 17400 KB n=2000
89 Correct 5 ms 17244 KB n=2000
90 Correct 6 ms 17232 KB n=2000
91 Correct 5 ms 17232 KB n=2000
92 Runtime error 26 ms 34196 KB Execution killed with signal 11
93 Halted 0 ms 0 KB -