oj.uz

Submission #334871

# Submission time Handle Problem Language Result Execution time Memory
334871 2020-12-10T06:44:36 Z tengiz05 Birthday gift (IZhO18_treearray) C++17
30 / 100
 4000 ms 5612 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
#define _ '_'<<
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int sz, n, m, k;
vector<int> edges[N];
int tin[N], tout[N];
int up[N][13];
int timer;
int depth[N];
void dfs(int u, int p, int d=0){
	tin[u] = timer++;
	depth[u] = d;
	up[u][0] = p;
	for(int i=1;i<13;i++)up[u][i] = up[up[u][i-1]][i-1];
	for(auto v : edges[u]){
		if(v != p){
			dfs(v, u,d+1);
		}
	}tout[u] = timer++;
}
bool isancestor(int u, int v){
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
	if(isancestor(u,v))return u;
	if(isancestor(v,u))return v;
	for(int i=12;i>=0;i--){
		if(!isancestor(up[u][i], v))u = up[u][i];
	}return up[u][0];
}
 
int t[N*4];
void update(int p, int val){
	t[p += sz] =val;
	//for(; p>1; p>>=1)t[p>>1] = lca(t[p], t[p^1]);
}
int rangelca(int l, int r){
	int ans = 0;
	for(l+=sz,r+=sz;l<=r;l>>=1,r>>=1){
		if(l%2==1){
			if(ans == 0)ans = t[l++];
			else ans = lca(ans, t[l++]);
		}if(r%2==0){
			if(ans == 0)ans = t[r--];
			else ans = lca(ans, t[r--]);
		}
	}return ans;
}
 
void solve(int test_case){
	int i, j, q;
	cin >> n >> m >> q;
	for(i=1;i<n;i++){
		int u, v;
		cin >> u >> v;
		edges[u].pb(v);
		edges[v].pb(u);
	}dfs(1,1);
	sz=1;
	while(sz <= m)sz<<=1;
	for(i=0;i<m;i++){
		cin >> t[i+sz];
	}for(i=sz-1;i>0;i--){
		t[i] = lca(t[i*2], t[i*2+1]);
	}
	while(q--){
		int type;
		cin >> type;
		if(type == 1){
			int pos, val;
			cin >> pos >> val;
			update(pos-1, val);
		}else {
			int l, r, v;
			cin >> l >> r >> v;
			l--,r--;
			bool flag = true;
			int L, R;
			int ansl=-2, ansr=-2;
			for(L=l; L <= r && flag; L++){
				int lc = t[L+sz];
				for(R=L; R <= r; R++){
					lc = lca(lc, t[R+sz]);
					if(lc == v){
						ansl = L, ansr = R;
						flag = false;
						break;
					}
				}
			}assert(ansl == -2 && ansr == -2 || ansl >= l && ansr <= r);
			cout << ansl+1 <<" "<< ansr+1 << '\n';
		/*	int L=l, R=l;
		
			for(;L <= r; L++){
				R = max(R, L);
				if(rangelca(L,R) == v){L++;break;}
				while(R+1 <= r && depth[lca(v, rangelca(L, R+1))] <= depth[v]){
					if(rangelca(L,R) == v){L++;break;}
					R++;
				}
				if(rangelca(L,R) == v){L++;break;}	
			}L--;
		//	cout << rangelca(L, R) << '\n';
			if(rangelca(L,R) == v)cout << L+1 << ' ' << R+1 << '\n';
			else cout << "-1 -1\n";*/
		}
	}
	return;
}
 
signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from treearray.cpp:1:
treearray.cpp: In function 'void solve(int)':
treearray.cpp:101:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  101 |    }assert(ansl == -2 && ansr == -2 || ansl >= l && ansr <= r);
      |            ~~~~~~~~~~~^~~~~~~~~~~~~
treearray.cpp:62:9: warning: unused variable 'j' [-Wunused-variable]
   62 |  int i, j, q;
      |         ^

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB n=5
2 Correct 4 ms 5100 KB n=100
3 Correct 5 ms 5100 KB n=100
4 Correct 4 ms 5100 KB n=100
5 Correct 4 ms 5100 KB n=100
6 Correct 6 ms 5100 KB n=100
7 Correct 5 ms 5100 KB n=100
8 Correct 4 ms 5100 KB n=100
9 Correct 4 ms 5100 KB n=100
10 Correct 5 ms 5100 KB n=100
11 Correct 5 ms 5100 KB n=100
12 Correct 4 ms 5100 KB n=100
13 Correct 4 ms 5100 KB n=100
14 Correct 4 ms 5100 KB n=100
15 Correct 4 ms 5100 KB n=100
16 Correct 4 ms 5120 KB n=100
17 Correct 4 ms 5100 KB n=100
18 Correct 4 ms 5120 KB n=100
19 Correct 4 ms 5112 KB n=100
20 Correct 4 ms 5100 KB n=100
21 Correct 4 ms 5100 KB n=100
22 Correct 4 ms 5100 KB n=100
23 Correct 4 ms 5100 KB n=100
24 Correct 4 ms 5100 KB n=100
25 Correct 4 ms 5100 KB n=100
26 Correct 3 ms 5100 KB n=12
27 Correct 5 ms 5100 KB n=100
28 Correct 4 ms 5100 KB n=500
29 Correct 21 ms 5100 KB n=500
30 Correct 17 ms 5100 KB n=500
31 Correct 19 ms 5116 KB n=500
32 Correct 5 ms 5100 KB n=500
33 Correct 17 ms 5100 KB n=500
34 Correct 4 ms 5100 KB n=500
35 Correct 18 ms 5100 KB n=500
36 Correct 188 ms 5100 KB n=500
37 Correct 187 ms 5100 KB n=500
38 Correct 184 ms 5100 KB n=500
39 Correct 31 ms 5100 KB n=500
40 Correct 30 ms 5100 KB n=500
41 Correct 29 ms 5100 KB n=500
42 Correct 94 ms 5500 KB n=500
43 Correct 94 ms 5100 KB n=500
44 Correct 92 ms 5100 KB n=500
45 Correct 4 ms 5100 KB n=500
46 Correct 19 ms 5100 KB n=500
47 Correct 18 ms 5100 KB n=500
48 Correct 4 ms 5100 KB n=500
49 Correct 16 ms 5100 KB n=500
50 Correct 28 ms 5100 KB n=500
51 Correct 28 ms 5100 KB n=500
52 Correct 32 ms 5100 KB n=500
53 Correct 29 ms 5100 KB n=500
54 Correct 17 ms 5228 KB n=500
55 Correct 7 ms 5100 KB n=278
56 Correct 100 ms 5100 KB n=500
57 Correct 101 ms 5100 KB n=500
58 Correct 85 ms 5100 KB n=500

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB n=5
2 Correct 4 ms 5100 KB n=100
3 Correct 5 ms 5100 KB n=100
4 Correct 4 ms 5100 KB n=100
5 Correct 4 ms 5100 KB n=100
6 Correct 6 ms 5100 KB n=100
7 Correct 5 ms 5100 KB n=100
8 Correct 4 ms 5100 KB n=100
9 Correct 4 ms 5100 KB n=100
10 Correct 5 ms 5100 KB n=100
11 Correct 5 ms 5100 KB n=100
12 Correct 4 ms 5100 KB n=100
13 Correct 4 ms 5100 KB n=100
14 Correct 4 ms 5100 KB n=100
15 Correct 4 ms 5100 KB n=100
16 Correct 4 ms 5120 KB n=100
17 Correct 4 ms 5100 KB n=100
18 Correct 4 ms 5120 KB n=100
19 Correct 4 ms 5112 KB n=100
20 Correct 4 ms 5100 KB n=100
21 Correct 4 ms 5100 KB n=100
22 Correct 4 ms 5100 KB n=100
23 Correct 4 ms 5100 KB n=100
24 Correct 4 ms 5100 KB n=100
25 Correct 4 ms 5100 KB n=100
26 Correct 3 ms 5100 KB n=12
27 Correct 5 ms 5100 KB n=100
28 Correct 4 ms 5100 KB n=500
29 Correct 21 ms 5100 KB n=500
30 Correct 17 ms 5100 KB n=500
31 Correct 19 ms 5116 KB n=500
32 Correct 5 ms 5100 KB n=500
33 Correct 17 ms 5100 KB n=500
34 Correct 4 ms 5100 KB n=500
35 Correct 18 ms 5100 KB n=500
36 Correct 188 ms 5100 KB n=500
37 Correct 187 ms 5100 KB n=500
38 Correct 184 ms 5100 KB n=500
39 Correct 31 ms 5100 KB n=500
40 Correct 30 ms 5100 KB n=500
41 Correct 29 ms 5100 KB n=500
42 Correct 94 ms 5500 KB n=500
43 Correct 94 ms 5100 KB n=500
44 Correct 92 ms 5100 KB n=500
45 Correct 4 ms 5100 KB n=500
46 Correct 19 ms 5100 KB n=500
47 Correct 18 ms 5100 KB n=500
48 Correct 4 ms 5100 KB n=500
49 Correct 16 ms 5100 KB n=500
50 Correct 28 ms 5100 KB n=500
51 Correct 28 ms 5100 KB n=500
52 Correct 32 ms 5100 KB n=500
53 Correct 29 ms 5100 KB n=500
54 Correct 17 ms 5228 KB n=500
55 Correct 7 ms 5100 KB n=278
56 Correct 100 ms 5100 KB n=500
57 Correct 101 ms 5100 KB n=500
58 Correct 85 ms 5100 KB n=500
59 Correct 20 ms 5356 KB n=2000
60 Correct 966 ms 5484 KB n=2000
61 Correct 909 ms 5484 KB n=2000
62 Correct 636 ms 5484 KB n=2000
63 Correct 25 ms 5356 KB n=2000
64 Correct 825 ms 5484 KB n=2000
65 Correct 8 ms 5228 KB n=2000
66 Correct 1049 ms 5612 KB n=2000
67 Correct 51 ms 5228 KB n=2000
68 Correct 843 ms 5484 KB n=2000
69 Execution timed out 4067 ms 5356 KB Time limit exceeded
70 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB n=5
2 Correct 4 ms 5100 KB n=100
3 Correct 5 ms 5100 KB n=100
4 Correct 4 ms 5100 KB n=100
5 Correct 4 ms 5100 KB n=100
6 Correct 6 ms 5100 KB n=100
7 Correct 5 ms 5100 KB n=100
8 Correct 4 ms 5100 KB n=100
9 Correct 4 ms 5100 KB n=100
10 Correct 5 ms 5100 KB n=100
11 Correct 5 ms 5100 KB n=100
12 Correct 4 ms 5100 KB n=100
13 Correct 4 ms 5100 KB n=100
14 Correct 4 ms 5100 KB n=100
15 Correct 4 ms 5100 KB n=100
16 Correct 4 ms 5120 KB n=100
17 Correct 4 ms 5100 KB n=100
18 Correct 4 ms 5120 KB n=100
19 Correct 4 ms 5112 KB n=100
20 Correct 4 ms 5100 KB n=100
21 Correct 4 ms 5100 KB n=100
22 Correct 4 ms 5100 KB n=100
23 Correct 4 ms 5100 KB n=100
24 Correct 4 ms 5100 KB n=100
25 Correct 4 ms 5100 KB n=100
26 Correct 3 ms 5100 KB n=12
27 Correct 5 ms 5100 KB n=100
28 Correct 4 ms 5100 KB n=500
29 Correct 21 ms 5100 KB n=500
30 Correct 17 ms 5100 KB n=500
31 Correct 19 ms 5116 KB n=500
32 Correct 5 ms 5100 KB n=500
33 Correct 17 ms 5100 KB n=500
34 Correct 4 ms 5100 KB n=500
35 Correct 18 ms 5100 KB n=500
36 Correct 188 ms 5100 KB n=500
37 Correct 187 ms 5100 KB n=500
38 Correct 184 ms 5100 KB n=500
39 Correct 31 ms 5100 KB n=500
40 Correct 30 ms 5100 KB n=500
41 Correct 29 ms 5100 KB n=500
42 Correct 94 ms 5500 KB n=500
43 Correct 94 ms 5100 KB n=500
44 Correct 92 ms 5100 KB n=500
45 Correct 4 ms 5100 KB n=500
46 Correct 19 ms 5100 KB n=500
47 Correct 18 ms 5100 KB n=500
48 Correct 4 ms 5100 KB n=500
49 Correct 16 ms 5100 KB n=500
50 Correct 28 ms 5100 KB n=500
51 Correct 28 ms 5100 KB n=500
52 Correct 32 ms 5100 KB n=500
53 Correct 29 ms 5100 KB n=500
54 Correct 17 ms 5228 KB n=500
55 Correct 7 ms 5100 KB n=278
56 Correct 100 ms 5100 KB n=500
57 Correct 101 ms 5100 KB n=500
58 Correct 85 ms 5100 KB n=500
59 Correct 20 ms 5356 KB n=2000
60 Correct 966 ms 5484 KB n=2000
61 Correct 909 ms 5484 KB n=2000
62 Correct 636 ms 5484 KB n=2000
63 Correct 25 ms 5356 KB n=2000
64 Correct 825 ms 5484 KB n=2000
65 Correct 8 ms 5228 KB n=2000
66 Correct 1049 ms 5612 KB n=2000
67 Correct 51 ms 5228 KB n=2000
68 Correct 843 ms 5484 KB n=2000
69 Execution timed out 4067 ms 5356 KB Time limit exceeded
70 Halted 0 ms 0 KB -