제출 #896384

#제출 시각아이디문제언어결과실행 시간메모리
896384GrindMachineTourism (JOI23_tourism)C++17
100 / 100
1263 ms64724 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* refs: https://codeforces.com/blog/entry/114003?#comment-1015100 */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; vector<int> adj1[N]; struct lca_algo { // LCA template (for graphs with 1-based indexing) int LOG = 1; vector<int> depth; vector<vector<int>> up; vector<int> tin, tout; int timer = 1; lca_algo() { } lca_algo(int n) { lca_init(n); } void lca_init(int n) { while ((1 << LOG) < n) LOG++; up = vector<vector<int>>(n + 1, vector<int>(LOG, 1)); depth = vector<int>(n + 1); tin = vector<int>(n + 1); tout = vector<int>(n + 1); lca_dfs(1, -1); } void lca_dfs(int node, int par) { tin[node] = timer++; trav(child, adj1[node]) { if (child == par) conts; up[child][0] = node; rep1(j, LOG - 1) { up[child][j] = up[up[child][j - 1]][j - 1]; } depth[child] = depth[node] + 1; lca_dfs(child, node); } tout[node] = timer-1; } int lift(int u, int k) { rep(j, LOG) { if (k & (1 << j)) { u = up[u][j]; } } return u; } int query(int u, int v) { if (depth[u] < depth[v]) swap(u, v); int k = depth[u] - depth[v]; u = lift(u, k); if (u == v) return u; rev(j, LOG - 1, 0) { if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; } } u = up[u][0]; return u; } int get_dis(int u, int v) { int lca = query(u, v); return depth[u] + depth[v] - 2 * depth[lca]; } bool is_ances(int u, int v){ return tin[u] <= tin[v] and tout[u] >= tout[v]; } }; template<typename T> struct fenwick { int siz; vector<T> tree; fenwick() { } fenwick(int n) { siz = n; tree = vector<T>(n + 1); } int lsb(int x) { return x & -x; } void build(vector<T> &a, int n) { for (int i = 1; i <= n; ++i) { int par = i + lsb(i); tree[i] += a[i]; if (par <= siz) { tree[par] += tree[i]; } } } void pupd(int i, T v) { while (i <= siz) { tree[i] += v; i += lsb(i); } } T sum(int i) { T res = 0; while (i) { res += tree[i]; i -= lsb(i); } return res; } T query(int l, int r) { if (l > r) return 0; T res = sum(r) - sum(l - 1); return res; } }; lca_algo LCA; vector<int> a(N); vector<pii> adj2[N]; vector<int> mxl(N), mnr(N); vector<array<int,3>> edge_contrib; void dfs1(int u, int p){ for(auto [v,d] : adj2[u]){ if(v == p) conts; dfs1(v,u); amax(mxl[u],mxl[v]); amin(mnr[u],mnr[v]); edge_contrib.pb({mxl[v],mnr[v],d}); } } vector<int> ans(N); vector<array<int,3>> here[N]; fenwick<int> fenw(N); void go(int l, int r, vector<array<int,3>> queries){ if(l > r) return; int mid = (l+r) >> 1; vector<array<int,3>> queries_left, queries_right, queries_curr; for(auto [ql,qr,id] : queries){ if(qr < mid){ queries_left.pb({ql,qr,id}); } else if(ql > mid){ queries_right.pb({ql,qr,id}); } else{ queries_curr.pb({ql,qr,id}); } } vector<pii> nodes; for(int i = l; i <= r; ++i){ int u = a[i]; nodes.pb({LCA.tin[u],u}); } sort(all(nodes)); int siz = sz(nodes); rep(i,siz-1){ int lca = LCA.query(nodes[i].ss,nodes[i+1].ss); nodes.pb({LCA.tin[lca],lca}); } sort(all(nodes)); nodes.resize(unique(all(nodes))-nodes.begin()); siz = sz(nodes); stack<int> stk; stk.push(nodes[0].ss); rep1(i,siz-1){ auto [ti,u] = nodes[i]; while(!LCA.is_ances(stk.top(),u)){ stk.pop(); } assert(!stk.empty()); int p = stk.top(); int d = LCA.get_dis(p,u); adj2[p].pb({u,d}), adj2[u].pb({p,d}); stk.push(u); } for(auto [ti,u] : nodes){ mxl[u] = 0; mnr[u] = r+1; } for(int i = l; i < mid; ++i){ int u = a[i]; amax(mxl[u],i); } for(int i = mid+1; i <= r; ++i){ int u = a[i]; amin(mnr[u],i); } edge_contrib.clear(); int root = a[mid]; dfs1(root,-1); for(auto [ql,qr,id] : queries_curr){ here[ql].pb({qr,id,1}); } for(auto [lx,rx,w] : edge_contrib){ here[lx].pb({rx,w,2}); } int sum = 0; for(auto [lx,rx,w] : edge_contrib){ if(lx >= l){ sum += w; } else{ fenw.pupd(rx,w); } } for(int ql = l; ql <= mid; ++ql){ trav(ar,here[ql]){ if(ar[2] == 1){ auto [qr,id,t] = ar; int res = sum+fenw.query(1,qr)+1; ans[id] = res; } else{ auto [rx,w,t] = ar; sum -= w; fenw.pupd(rx,w); } } } // reset for(auto [ql,qr,id] : queries_curr){ here[ql].clear(); } for(auto [lx,rx,w] : edge_contrib){ here[lx].clear(); } for(auto [ti,u] : nodes){ adj2[u].clear(); } for(auto [lx,rx,w] : edge_contrib){ fenw.pupd(rx,-w); } go(l,mid-1,queries_left); go(mid+1,r,queries_right); } void solve(int test_case) { int n,m,q; cin >> n >> m >> q; rep1(i,n-1){ int u,v; cin >> u >> v; adj1[u].pb(v), adj1[v].pb(u); } rep1(i,m) cin >> a[i]; LCA = lca_algo(n); vector<array<int,3>> queries; rep1(i,q){ int l,r; cin >> l >> r; queries.pb({l,r,i}); } go(1,m,queries); rep1(i,q) cout << ans[i] << endl; } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } 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...