Submission #804467

#TimeUsernameProblemLanguageResultExecution timeMemory
804467mousebeaverTourism (JOI23_tourism)C++14
0 / 100
1 ms468 KiB
#define ll long long #define pll pair<ll, ll> #define INF numeric_limits<int>::max()/2 #include <bits/stdc++.h> using namespace std; void init(ll i, vector<ll>& depth, vector<vector<ll>>& adjlist, vector<bool>& visited, vector<ll>& subtree, vector<vector<ll>>& jump) { visited[i] = true; for(ll j : adjlist[i]) { if(visited[j]) { jump[0][i] = j; depth[i] = depth[j]+1; } } for(ll j : adjlist[i]) { if(!visited[j]) { init(j, depth, adjlist, visited, subtree, jump); subtree[i] += subtree[j]; } } } ll lift(ll a, vector<vector<ll>>& jump, ll dist) { for(ll i = jump.size()-1; i >= 0 && a != -1; i--) { if(((1<<i)&dist) != 0) { a = jump[i][a]; } } return a; } ll lca(ll a, ll b, vector<vector<ll>>& jump, vector<ll>& depth) { if(depth[a] < depth[b]) swap(a, b); a = lift(a, jump, depth[a]-depth[b]); if(a == b) { return a; } for(ll j = jump.size()-1; j >= 0; j--) { if(jump[j][a] != jump[j][b]) { a = jump[j][a]; b = jump[j][b]; } } return jump[0][a]; } ll left(ll i) { return 2*i; } ll right(ll i) { return 2*i+1; } pll conjugate(pll a, pll b) { return {max(a.first, b.first), min(a.second, b.second)}; } pll query3(ll i, vector<pll>& s, ll a, ll b, ll l, ll r) { if(l <= a && b <= r) { return s[i]; } if(b < l || r < a) { return {-1, INF}; } ll mid = (a+b)/2; return conjugate(query3(left(i), s, a, mid, l, r), query3(right(i), s, mid+1, b, l, r)); } int main() { ios::sync_with_stdio(false); cin.tie(0); ll n, m, q; cin>>n>>m>>q; vector<vector<ll>> adjlist(n, vector<ll> (0)); bool sub3 = true; for(ll i = 0; i < n-1; i++) { ll a, b; cin>>a>>b; a--; b--; if(a != i || b != i+1) { sub3 = false; } adjlist[a].push_back(b); adjlist[b].push_back(a); } ll segnodes = 1; ll logdepth = 0; while(2*n > segnodes) { segnodes *= 2; logdepth++; } vector<vector<ll>> jump(logdepth, vector<ll> (n, -1)); vector<ll> subtree(n, 1); vector<bool> visited(n, false); vector<ll> depth(n, 0); init(0, depth, adjlist, visited, subtree, jump); for(ll i = 1; i < logdepth; i++) { for(ll j = 0; j < n; j++) { if(jump[i-1][j] != -1) { jump[i][j] = jump[i-1][jump[i-1][j]]; } } } vector<ll> c(m); for(ll i = 0; i < m; i++) { cin>>c[i]; c[i]--; } vector<pll> s3(segnodes, {-1, INF}); //Max, min if(sub3) { for(ll i = 0; i < n; i++) { s3[i+segnodes/2].first = depth[c[i]]; s3[i+segnodes/2].second = depth[c[i]]; } for(ll i = segnodes/2-1; i > 0; i--) { s3[i].first = max(s3[left(i)].first, s3[right(i)].first); s3[i].second = min(s3[left(i)].second, s3[right(i)].second); } } assert(sub3); for(ll x = 0; x < q; x++) { ll left, right; cin>>left>>right; left--; right--; if(left == right) { cout<<1<<"\n"; continue; } if(sub3) { pll range = query3(1, s3, 1, segnodes/2, left+1, right+1); cout<<range.first+1-range.second<<"\n"; continue; } ll l = lca(c[left], c[left+1], jump, depth); for(ll i = left+2; i <= right; i++) { l = lca(l, c[i], jump, depth); } visited.assign(n, false); visited[l] = true; ll counter = 1; for(ll i = left; i <= right; i++) { ll node = c[i]; while(!visited[node]) { visited[node] = true; counter++; node = jump[0][node]; } } cout<<counter<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...