oj.uz

Submission #889632

# Submission time Handle Problem Language Result Execution time Memory
889632 2023-12-20T04:09:22 Z vjudge1 Tourism (JOI23_tourism) C++17
18 / 100
 5000 ms 44612 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[mn] - depth[mx] + 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Incorrect 1 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Incorrect 1 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 71 ms 26968 KB Output is correct
3 Correct 103 ms 37320 KB Output is correct
4 Correct 88 ms 32964 KB Output is correct
5 Correct 85 ms 44612 KB Output is correct
6 Correct 86 ms 43976 KB Output is correct
7 Correct 96 ms 43716 KB Output is correct
8 Correct 105 ms 43720 KB Output is correct
9 Correct 127 ms 43836 KB Output is correct
10 Correct 128 ms 43720 KB Output is correct
11 Correct 147 ms 43720 KB Output is correct
12 Correct 138 ms 43976 KB Output is correct
13 Correct 141 ms 43716 KB Output is correct
14 Correct 150 ms 43968 KB Output is correct
15 Correct 92 ms 43972 KB Output is correct
16 Correct 136 ms 44164 KB Output is correct
17 Correct 119 ms 44028 KB Output is correct
18 Correct 115 ms 44432 KB Output is correct
19 Correct 76 ms 44488 KB Output is correct
20 Correct 77 ms 44416 KB Output is correct
21 Correct 81 ms 43912 KB Output is correct
22 Correct 92 ms 43728 KB Output is correct
23 Correct 110 ms 43712 KB Output is correct
24 Correct 149 ms 43720 KB Output is correct
25 Correct 202 ms 43828 KB Output is correct
26 Correct 264 ms 43696 KB Output is correct
27 Correct 362 ms 43980 KB Output is correct
28 Correct 422 ms 43820 KB Output is correct
29 Correct 574 ms 44104 KB Output is correct
30 Correct 700 ms 44124 KB Output is correct
31 Correct 788 ms 43984 KB Output is correct
32 Correct 949 ms 43976 KB Output is correct
33 Correct 727 ms 43896 KB Output is correct
34 Correct 94 ms 44024 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 2 ms 5476 KB Output is correct
4 Execution timed out 5090 ms 38308 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 Incorrect 1 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -