답안 #685129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
685129	2023-01-23T14:33:03 Z	Nuraly_Serikbay	Birthday gift (IZhO18_treearray)	C++14	56 / 100	206 ms	952 KB

treearray

/* Speech to the young */

//#include <bits/stdc++.h>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
/*
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse,-fgcse-lm")
#pragma GCC optimize("-ftree-pre,-ftree-vrp")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
*/
 

using namespace std;

#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0)
#define int long long
#define cube (x) ((x) * (x) * (x))

int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}}
void pre(int a) { cout<<fixed<<setprecision(a); }
int bitcount (int x) {return __builtin_popcount	(x);}

const int N = 2e6 + 10;
const int INF = 1e18 + 1;
const int MOD = 1e9 + 7;
const int P = 31;
const double eps = 1e-19;
long double pi = 3.1415926535897323;

int n, m, q, depth[2005], up[2005][20], a[2005];
vector <int> g[2005];

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

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

void Solution () {
	cin >> n >> m >> q;
	int x, y;
	for (int i = 1; i < n; ++ i) {
		cin >> x >> y;
		g[x].pb (y), g[y].pb (x);
	}
	dfs (1, 0);
	for (int i = 1; i <= m; ++ i) cin >> a[i];
	while (q --) {
		int tp, l, r, v, pos;
		cin >> tp;
		if (tp == 1) {
			cin >> pos >> v;
			a[pos] = v;
		} else {
			cin >> l >> r >> v;
			pair <int, int> ans;
			int x = 0, bg = 0;
			for (int i = l; i <= r; ++ i) {
				if (lca (v, a[i]) == v) {
					if (!x) {
						x = a[i];
						bg = i;
					}
					else x = lca (x, a[i]);
					if (x == v) {
						ans = {bg, i};
						break;
					}
				} else x = 0;
				
			}
			if (ans.F == 0 && ans.S == 0) {
				cout << "-1 -1\n";
			} else cout << ans.F << ' ' << ans.S << '\n';
			
		}
	}
	
}

signed main () {
	YOSIK();
//	precalc();
	int T = 1;
//	cin >> T;
	while (T --) Solution ();
	exit (0);
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	n=5
2	Correct	0 ms	340 KB	n=100
3	Correct	1 ms	340 KB	n=100
4	Correct	1 ms	340 KB	n=100
5	Correct	1 ms	340 KB	n=100
6	Correct	1 ms	340 KB	n=100
7	Correct	1 ms	340 KB	n=100
8	Correct	1 ms	340 KB	n=100
9	Correct	1 ms	340 KB	n=100
10	Correct	1 ms	340 KB	n=100
11	Correct	1 ms	340 KB	n=100
12	Correct	1 ms	340 KB	n=100
13	Correct	0 ms	340 KB	n=100
14	Correct	1 ms	340 KB	n=100
15	Correct	0 ms	340 KB	n=100
16	Correct	1 ms	340 KB	n=100
17	Correct	1 ms	404 KB	n=100
18	Correct	1 ms	340 KB	n=100
19	Correct	1 ms	340 KB	n=100
20	Correct	1 ms	340 KB	n=100
21	Correct	1 ms	340 KB	n=100
22	Correct	1 ms	340 KB	n=100
23	Correct	1 ms	340 KB	n=100
24	Correct	1 ms	340 KB	n=100
25	Correct	1 ms	340 KB	n=100
26	Correct	1 ms	340 KB	n=12
27	Correct	1 ms	340 KB	n=100
28	Correct	1 ms	468 KB	n=500
29	Correct	3 ms	468 KB	n=500
30	Correct	2 ms	468 KB	n=500
31	Correct	4 ms	492 KB	n=500
32	Correct	1 ms	468 KB	n=500
33	Correct	2 ms	492 KB	n=500
34	Correct	1 ms	468 KB	n=500
35	Correct	3 ms	468 KB	n=500
36	Correct	7 ms	488 KB	n=500
37	Correct	9 ms	488 KB	n=500
38	Correct	8 ms	492 KB	n=500
39	Correct	4 ms	468 KB	n=500
40	Correct	4 ms	468 KB	n=500
41	Correct	4 ms	468 KB	n=500
42	Correct	4 ms	468 KB	n=500
43	Correct	4 ms	468 KB	n=500
44	Correct	5 ms	468 KB	n=500
45	Correct	1 ms	468 KB	n=500
46	Correct	3 ms	500 KB	n=500
47	Correct	2 ms	468 KB	n=500
48	Correct	1 ms	468 KB	n=500
49	Correct	2 ms	504 KB	n=500
50	Correct	3 ms	468 KB	n=500
51	Correct	3 ms	468 KB	n=500
52	Correct	4 ms	468 KB	n=500
53	Correct	4 ms	492 KB	n=500
54	Correct	6 ms	468 KB	n=500
55	Correct	1 ms	340 KB	n=278
56	Correct	9 ms	468 KB	n=500
57	Correct	10 ms	468 KB	n=500
58	Correct	10 ms	468 KB	n=500
59	Correct	2 ms	724 KB	n=2000
60	Correct	34 ms	852 KB	n=2000
61	Correct	33 ms	888 KB	n=2000
62	Correct	23 ms	852 KB	n=2000
63	Correct	2 ms	768 KB	n=2000
64	Correct	30 ms	852 KB	n=2000
65	Correct	2 ms	772 KB	n=2000
66	Correct	37 ms	884 KB	n=2000
67	Correct	5 ms	768 KB	n=2000
68	Correct	31 ms	852 KB	n=2000
69	Correct	111 ms	844 KB	n=2000
70	Correct	112 ms	852 KB	n=2000
71	Correct	108 ms	952 KB	n=2000
72	Correct	58 ms	844 KB	n=2000
73	Correct	56 ms	848 KB	n=2000
74	Correct	2 ms	724 KB	n=1844
75	Correct	57 ms	852 KB	n=2000
76	Correct	64 ms	828 KB	n=2000
77	Correct	63 ms	924 KB	n=2000
78	Correct	68 ms	828 KB	n=2000
79	Correct	2 ms	852 KB	n=2000
80	Correct	31 ms	852 KB	n=2000
81	Correct	27 ms	852 KB	n=2000
82	Correct	2 ms	896 KB	n=2000
83	Correct	30 ms	852 KB	n=2000
84	Correct	46 ms	852 KB	n=2000
85	Correct	52 ms	852 KB	n=2000
86	Correct	54 ms	872 KB	n=2000
87	Correct	46 ms	724 KB	n=2000
88	Correct	206 ms	912 KB	n=2000
89	Correct	204 ms	852 KB	n=2000
90	Correct	101 ms	908 KB	n=2000
91	Correct	122 ms	844 KB	n=2000

Subtask #4
0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	n=5
2	Correct	0 ms	340 KB	n=100
3	Correct	1 ms	340 KB	n=100
4	Correct	1 ms	340 KB	n=100
5	Correct	1 ms	340 KB	n=100
6	Correct	1 ms	340 KB	n=100
7	Correct	1 ms	340 KB	n=100
8	Correct	1 ms	340 KB	n=100
9	Correct	1 ms	340 KB	n=100
10	Correct	1 ms	340 KB	n=100
11	Correct	1 ms	340 KB	n=100
12	Correct	1 ms	340 KB	n=100
13	Correct	0 ms	340 KB	n=100
14	Correct	1 ms	340 KB	n=100
15	Correct	0 ms	340 KB	n=100
16	Correct	1 ms	340 KB	n=100
17	Correct	1 ms	404 KB	n=100
18	Correct	1 ms	340 KB	n=100
19	Correct	1 ms	340 KB	n=100
20	Correct	1 ms	340 KB	n=100
21	Correct	1 ms	340 KB	n=100
22	Correct	1 ms	340 KB	n=100
23	Correct	1 ms	340 KB	n=100
24	Correct	1 ms	340 KB	n=100
25	Correct	1 ms	340 KB	n=100
26	Correct	1 ms	340 KB	n=12
27	Correct	1 ms	340 KB	n=100
28	Correct	1 ms	468 KB	n=500
29	Correct	3 ms	468 KB	n=500
30	Correct	2 ms	468 KB	n=500
31	Correct	4 ms	492 KB	n=500
32	Correct	1 ms	468 KB	n=500
33	Correct	2 ms	492 KB	n=500
34	Correct	1 ms	468 KB	n=500
35	Correct	3 ms	468 KB	n=500
36	Correct	7 ms	488 KB	n=500
37	Correct	9 ms	488 KB	n=500
38	Correct	8 ms	492 KB	n=500
39	Correct	4 ms	468 KB	n=500
40	Correct	4 ms	468 KB	n=500
41	Correct	4 ms	468 KB	n=500
42	Correct	4 ms	468 KB	n=500
43	Correct	4 ms	468 KB	n=500
44	Correct	5 ms	468 KB	n=500
45	Correct	1 ms	468 KB	n=500
46	Correct	3 ms	500 KB	n=500
47	Correct	2 ms	468 KB	n=500
48	Correct	1 ms	468 KB	n=500
49	Correct	2 ms	504 KB	n=500
50	Correct	3 ms	468 KB	n=500
51	Correct	3 ms	468 KB	n=500
52	Correct	4 ms	468 KB	n=500
53	Correct	4 ms	492 KB	n=500
54	Correct	6 ms	468 KB	n=500
55	Correct	1 ms	340 KB	n=278
56	Correct	9 ms	468 KB	n=500
57	Correct	10 ms	468 KB	n=500
58	Correct	10 ms	468 KB	n=500
59	Correct	2 ms	724 KB	n=2000
60	Correct	34 ms	852 KB	n=2000
61	Correct	33 ms	888 KB	n=2000
62	Correct	23 ms	852 KB	n=2000
63	Correct	2 ms	768 KB	n=2000
64	Correct	30 ms	852 KB	n=2000
65	Correct	2 ms	772 KB	n=2000
66	Correct	37 ms	884 KB	n=2000
67	Correct	5 ms	768 KB	n=2000
68	Correct	31 ms	852 KB	n=2000
69	Correct	111 ms	844 KB	n=2000
70	Correct	112 ms	852 KB	n=2000
71	Correct	108 ms	952 KB	n=2000
72	Correct	58 ms	844 KB	n=2000
73	Correct	56 ms	848 KB	n=2000
74	Correct	2 ms	724 KB	n=1844
75	Correct	57 ms	852 KB	n=2000
76	Correct	64 ms	828 KB	n=2000
77	Correct	63 ms	924 KB	n=2000
78	Correct	68 ms	828 KB	n=2000
79	Correct	2 ms	852 KB	n=2000
80	Correct	31 ms	852 KB	n=2000
81	Correct	27 ms	852 KB	n=2000
82	Correct	2 ms	896 KB	n=2000
83	Correct	30 ms	852 KB	n=2000
84	Correct	46 ms	852 KB	n=2000
85	Correct	52 ms	852 KB	n=2000
86	Correct	54 ms	872 KB	n=2000
87	Correct	46 ms	724 KB	n=2000
88	Correct	206 ms	912 KB	n=2000
89	Correct	204 ms	852 KB	n=2000
90	Correct	101 ms	908 KB	n=2000
91	Correct	122 ms	844 KB	n=2000
92	Runtime error	1 ms	596 KB	Execution killed with signal 11
93	Halted	0 ms	0 KB	-

답안 #685129

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 18.0 / 18.0

Subtask #3 26.0 / 26.0

Subtask #4 0 / 44.0

Subtask #1
12.0 / 12.0

Subtask #2
18.0 / 18.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 44.0