oj.uz

Submission #889635

# Submission time Handle Problem Language Result Execution time Memory
889635 2023-12-20T04:10:49 Z vjudge1 Tourism (JOI23_tourism) C++17
35 / 100
 5000 ms 50716 KB 
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 998244353;
const int N = 1e5;


pair<int, int> chmax(pair<int, int> A, pair<int, int> B){
	if(A.ff > B.ff) return A;
	return B;
}

pair<int, int> chmin(pair<int, int> A, pair<int, int> B){
	if(A.ff > B.ff) return B;
	return A;
}

struct sparse{
	vector<vector<pair<int, int> > > m_table;
	vector<vector<pair<int, int> > >  ma_table;
	int n;
	
	sparse(int sz){
		n = sz;
		m_table.resize(18);
		ma_table.resize(18);
		for(auto &i : m_table){
			i.resize(sz);
		} 
		for(auto &i : ma_table) i.resize(sz);
	};
	
	void build(vector<pair<int, int>> &a){
		for(int lg = 0; lg < 18; lg++){
			for(int i = 0;i < n; i++){
				if(lg == 0){
					m_table[lg][i] = a[i];
					ma_table[lg][i] = a[i];
				}else{
					int k = 1<<(lg-1);
					m_table[lg][i] = chmin(m_table[lg-1][i], m_table[lg-1][min(n - 1, i +  k)]);
					ma_table[lg][i] = chmax(ma_table[lg-1][i], ma_table[lg-1][min(n - 1, i +  k)]);
				}
			}
		}
	}
	
	pair<int, int> get_max(int l, int r){
		int k = __lg(r-l+1);
		return chmax(ma_table[k][l], ma_table[k][r-(1<<k) + 1]);
	}
	
	pair<int, int> get_min(int l, int r){
		int k = __lg(r-l+1);
		return chmin(m_table[k][l], m_table[k][r-(1<<k) + 1]);
	}
	
		
};





vector<int> g[N+1];
int depth[N+1], c[N+1];
int timer=1;
int tin[N+1], tout[N+1];
int up[N+1][18];
int n, m, q;

void dfs(int v, int par){
	up[v][0] = par;
	tin[v] = timer++;
	for(int i = 1;i < 18; i++){
		up[v][i] = up[up[v][i-1]][i-1];
	}
	for(int to : g[v]){
		if(to == par) continue;
		depth[to] = depth[v] + 1;
		dfs(to, v);
	}
	tout[v] = timer++;
}

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

int vert;
vector<int> vec;


int in_subtree(int v){
	int it = lower_bound(all(vec), tin[v]) - vec.begin();
	if(it < (int)vec.size() && vec[it] <= tout[v]) return 1;
	return 0;
}

void ans(int v, int par){
	if(!in_subtree(v)) return;
	vert++;
	for(int to : g[v]){
		if(to == par) continue;
		ans(to, v);
	}
}





signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	 cin >> n >> m >> q;
	 int bambo = 1;
	for(int i = 1;i < n; i++){
		int a, b; cin >> a >> b;
		if(a != i || b != a+1) bambo = 0;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i = 0;i < m; i++){
		cin >> c[i];
	}
	dfs(1, 1);
	vector<pair<int, int> > vals;
	for(int i = 0;i < m; i++){
		vals.push_back(make_pair(tin[c[i]], c[i]));
	}
	sparse table(m);
	table.build(vals);
	if(bambo){
		
		while(q--){
			int l, r; cin >> l >> r;
			l--, r--;
			int mn = table.get_min(l, r).ss;
			int mx = table.get_max(l, r).ss;
			cout << depth[mx] - depth[mn]  + 1 << '\n';
			
		}
		
		return 0;
	}
	while(q--){
		int l, r; cin >> l >> r;
		l--, r--;
		int mn = c[l], mx = c[l];
		vec.clear();
		for(int i = l;i <= r; i++){
			vec.push_back(tin[c[i]]);
			if(tin[mn] > tin[c[i]]){
				mn = c[i];
			}
			if(tin[mx] < tin[c[i]]){
				mx = c[i];
			}
		}
		
		mn = table.get_min(l, r).ss;
		mx = table.get_max(l, r).ss;
		sort(all(vec));
		vec.erase(unique(all(vec)), vec.end());
		vert = 0;
		int lc = lca(mn, mx);
		ans(lc, up[lc][0]);
		
		cout << vert << '\n';
		
	}
	
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 5084 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 5 ms 4952 KB Output is correct
10 Correct 4 ms 5212 KB Output is correct
11 Correct 5 ms 5212 KB Output is correct
12 Correct 6 ms 5212 KB Output is correct
13 Correct 6 ms 5208 KB Output is correct
14 Correct 6 ms 5212 KB Output is correct
15 Correct 4 ms 5212 KB Output is correct
16 Correct 4 ms 5212 KB Output is correct
17 Correct 4 ms 5212 KB Output is correct
18 Correct 5 ms 5464 KB Output is correct
19 Correct 4 ms 5212 KB Output is correct
20 Correct 4 ms 5224 KB Output is correct
21 Correct 4 ms 5212 KB Output is correct
22 Correct 4 ms 5212 KB Output is correct
23 Correct 4 ms 5224 KB Output is correct
24 Correct 4 ms 5212 KB Output is correct
25 Correct 4 ms 5220 KB Output is correct
26 Correct 4 ms 5208 KB Output is correct
27 Correct 1 ms 4956 KB Output is correct
28 Correct 1 ms 4956 KB Output is correct
29 Correct 1 ms 5212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 5084 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 5 ms 4952 KB Output is correct
10 Correct 4 ms 5212 KB Output is correct
11 Correct 5 ms 5212 KB Output is correct
12 Correct 6 ms 5212 KB Output is correct
13 Correct 6 ms 5208 KB Output is correct
14 Correct 6 ms 5212 KB Output is correct
15 Correct 4 ms 5212 KB Output is correct
16 Correct 4 ms 5212 KB Output is correct
17 Correct 4 ms 5212 KB Output is correct
18 Correct 5 ms 5464 KB Output is correct
19 Correct 4 ms 5212 KB Output is correct
20 Correct 4 ms 5224 KB Output is correct
21 Correct 4 ms 5212 KB Output is correct
22 Correct 4 ms 5212 KB Output is correct
23 Correct 4 ms 5224 KB Output is correct
24 Correct 4 ms 5212 KB Output is correct
25 Correct 4 ms 5220 KB Output is correct
26 Correct 4 ms 5208 KB Output is correct
27 Correct 1 ms 4956 KB Output is correct
28 Correct 1 ms 4956 KB Output is correct
29 Correct 1 ms 5212 KB Output is correct
30 Correct 89 ms 5464 KB Output is correct
31 Correct 124 ms 5724 KB Output is correct
32 Correct 185 ms 5720 KB Output is correct
33 Correct 184 ms 5880 KB Output is correct
34 Correct 194 ms 5984 KB Output is correct
35 Correct 366 ms 5880 KB Output is correct
36 Correct 372 ms 5904 KB Output is correct
37 Correct 365 ms 5724 KB Output is correct
38 Correct 174 ms 5724 KB Output is correct
39 Correct 181 ms 5980 KB Output is correct
40 Correct 168 ms 5976 KB Output is correct
41 Correct 337 ms 5984 KB Output is correct
42 Correct 340 ms 5980 KB Output is correct
43 Correct 340 ms 5724 KB Output is correct
44 Correct 171 ms 5724 KB Output is correct
45 Correct 168 ms 5908 KB Output is correct
46 Correct 174 ms 5724 KB Output is correct
47 Correct 354 ms 5972 KB Output is correct
48 Correct 336 ms 5720 KB Output is correct
49 Correct 336 ms 5912 KB Output is correct
50 Correct 173 ms 5724 KB Output is correct
51 Correct 181 ms 5892 KB Output is correct
52 Correct 187 ms 5968 KB Output is correct
53 Correct 178 ms 5884 KB Output is correct
54 Correct 179 ms 5884 KB Output is correct
55 Correct 176 ms 5908 KB Output is correct
56 Correct 2 ms 5468 KB Output is correct
57 Correct 2 ms 5212 KB Output is correct
58 Correct 2 ms 5724 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 2 ms 5468 KB Output is correct
4 Correct 60 ms 40868 KB Output is correct
5 Correct 51 ms 35792 KB Output is correct
6 Correct 58 ms 44300 KB Output is correct
7 Correct 82 ms 50560 KB Output is correct
8 Correct 76 ms 50388 KB Output is correct
9 Correct 96 ms 50376 KB Output is correct
10 Correct 77 ms 50716 KB Output is correct
11 Correct 81 ms 50384 KB Output is correct
12 Correct 83 ms 50580 KB Output is correct
13 Correct 72 ms 50380 KB Output is correct
14 Correct 73 ms 50372 KB Output is correct
15 Correct 41 ms 20820 KB Output is correct
16 Correct 93 ms 49984 KB Output is correct
17 Correct 45 ms 34264 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 98 ms 27132 KB Output is correct
3 Correct 119 ms 37180 KB Output is correct
4 Correct 93 ms 33124 KB Output is correct
5 Correct 106 ms 44484 KB Output is correct
6 Correct 113 ms 43980 KB Output is correct
7 Correct 114 ms 43720 KB Output is correct
8 Correct 133 ms 43680 KB Output is correct
9 Correct 189 ms 43844 KB Output is correct
10 Correct 159 ms 43844 KB Output is correct
11 Correct 171 ms 43720 KB Output is correct
12 Correct 166 ms 43792 KB Output is correct
13 Correct 167 ms 43684 KB Output is correct
14 Correct 166 ms 43772 KB Output is correct
15 Correct 100 ms 43964 KB Output is correct
16 Correct 128 ms 44164 KB Output is correct
17 Correct 149 ms 44148 KB Output is correct
18 Correct 154 ms 44088 KB Output is correct
19 Correct 75 ms 44488 KB Output is correct
20 Correct 75 ms 44188 KB Output is correct
21 Correct 106 ms 43720 KB Output is correct
22 Correct 92 ms 43716 KB Output is correct
23 Correct 115 ms 43652 KB Output is correct
24 Correct 180 ms 43836 KB Output is correct
25 Correct 232 ms 43832 KB Output is correct
26 Correct 267 ms 43872 KB Output is correct
27 Correct 402 ms 43860 KB Output is correct
28 Correct 533 ms 43720 KB Output is correct
29 Correct 639 ms 43652 KB Output is correct
30 Correct 838 ms 43920 KB Output is correct
31 Correct 854 ms 43896 KB Output is correct
32 Correct 911 ms 43900 KB Output is correct
33 Correct 698 ms 44112 KB Output is correct
34 Correct 92 ms 43972 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 3 ms 5464 KB Output is correct
4 Execution timed out 5076 ms 38280 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 5084 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 5 ms 4952 KB Output is correct
10 Correct 4 ms 5212 KB Output is correct
11 Correct 5 ms 5212 KB Output is correct
12 Correct 6 ms 5212 KB Output is correct
13 Correct 6 ms 5208 KB Output is correct
14 Correct 6 ms 5212 KB Output is correct
15 Correct 4 ms 5212 KB Output is correct
16 Correct 4 ms 5212 KB Output is correct
17 Correct 4 ms 5212 KB Output is correct
18 Correct 5 ms 5464 KB Output is correct
19 Correct 4 ms 5212 KB Output is correct
20 Correct 4 ms 5224 KB Output is correct
21 Correct 4 ms 5212 KB Output is correct
22 Correct 4 ms 5212 KB Output is correct
23 Correct 4 ms 5224 KB Output is correct
24 Correct 4 ms 5212 KB Output is correct
25 Correct 4 ms 5220 KB Output is correct
26 Correct 4 ms 5208 KB Output is correct
27 Correct 1 ms 4956 KB Output is correct
28 Correct 1 ms 4956 KB Output is correct
29 Correct 1 ms 5212 KB Output is correct
30 Correct 89 ms 5464 KB Output is correct
31 Correct 124 ms 5724 KB Output is correct
32 Correct 185 ms 5720 KB Output is correct
33 Correct 184 ms 5880 KB Output is correct
34 Correct 194 ms 5984 KB Output is correct
35 Correct 366 ms 5880 KB Output is correct
36 Correct 372 ms 5904 KB Output is correct
37 Correct 365 ms 5724 KB Output is correct
38 Correct 174 ms 5724 KB Output is correct
39 Correct 181 ms 5980 KB Output is correct
40 Correct 168 ms 5976 KB Output is correct
41 Correct 337 ms 5984 KB Output is correct
42 Correct 340 ms 5980 KB Output is correct
43 Correct 340 ms 5724 KB Output is correct
44 Correct 171 ms 5724 KB Output is correct
45 Correct 168 ms 5908 KB Output is correct
46 Correct 174 ms 5724 KB Output is correct
47 Correct 354 ms 5972 KB Output is correct
48 Correct 336 ms 5720 KB Output is correct
49 Correct 336 ms 5912 KB Output is correct
50 Correct 173 ms 5724 KB Output is correct
51 Correct 181 ms 5892 KB Output is correct
52 Correct 187 ms 5968 KB Output is correct
53 Correct 178 ms 5884 KB Output is correct
54 Correct 179 ms 5884 KB Output is correct
55 Correct 176 ms 5908 KB Output is correct
56 Correct 2 ms 5468 KB Output is correct
57 Correct 2 ms 5212 KB Output is correct
58 Correct 2 ms 5724 KB Output is correct
59 Correct 1 ms 4956 KB Output is correct
60 Correct 1 ms 4956 KB Output is correct
61 Correct 2 ms 5468 KB Output is correct
62 Correct 60 ms 40868 KB Output is correct
63 Correct 51 ms 35792 KB Output is correct
64 Correct 58 ms 44300 KB Output is correct
65 Correct 82 ms 50560 KB Output is correct
66 Correct 76 ms 50388 KB Output is correct
67 Correct 96 ms 50376 KB Output is correct
68 Correct 77 ms 50716 KB Output is correct
69 Correct 81 ms 50384 KB Output is correct
70 Correct 83 ms 50580 KB Output is correct
71 Correct 72 ms 50380 KB Output is correct
72 Correct 73 ms 50372 KB Output is correct
73 Correct 41 ms 20820 KB Output is correct
74 Correct 93 ms 49984 KB Output is correct
75 Correct 45 ms 34264 KB Output is correct
76 Correct 1 ms 4952 KB Output is correct
77 Correct 98 ms 27132 KB Output is correct
78 Correct 119 ms 37180 KB Output is correct
79 Correct 93 ms 33124 KB Output is correct
80 Correct 106 ms 44484 KB Output is correct
81 Correct 113 ms 43980 KB Output is correct
82 Correct 114 ms 43720 KB Output is correct
83 Correct 133 ms 43680 KB Output is correct
84 Correct 189 ms 43844 KB Output is correct
85 Correct 159 ms 43844 KB Output is correct
86 Correct 171 ms 43720 KB Output is correct
87 Correct 166 ms 43792 KB Output is correct
88 Correct 167 ms 43684 KB Output is correct
89 Correct 166 ms 43772 KB Output is correct
90 Correct 100 ms 43964 KB Output is correct
91 Correct 128 ms 44164 KB Output is correct
92 Correct 149 ms 44148 KB Output is correct
93 Correct 154 ms 44088 KB Output is correct
94 Correct 75 ms 44488 KB Output is correct
95 Correct 75 ms 44188 KB Output is correct
96 Correct 106 ms 43720 KB Output is correct
97 Correct 92 ms 43716 KB Output is correct
98 Correct 115 ms 43652 KB Output is correct
99 Correct 180 ms 43836 KB Output is correct
100 Correct 232 ms 43832 KB Output is correct
101 Correct 267 ms 43872 KB Output is correct
102 Correct 402 ms 43860 KB Output is correct
103 Correct 533 ms 43720 KB Output is correct
104 Correct 639 ms 43652 KB Output is correct
105 Correct 838 ms 43920 KB Output is correct
106 Correct 854 ms 43896 KB Output is correct
107 Correct 911 ms 43900 KB Output is correct
108 Correct 698 ms 44112 KB Output is correct
109 Correct 92 ms 43972 KB Output is correct
110 Correct 1 ms 4956 KB Output is correct
111 Correct 1 ms 4956 KB Output is correct
112 Correct 3 ms 5464 KB Output is correct
113 Execution timed out 5076 ms 38280 KB Time limit exceeded
114 Halted 0 ms 0 KB -