Submission #1013721

#TimeUsernameProblemLanguageResultExecution timeMemory
101372112345678Tourism (JOI23_tourism)C++17
18 / 100
652 ms19540 KiB
#include <bits/stdc++.h> using namespace std; const int nx=1e5+5, kx=17; int n, m, q, u, v, in[nx], out[nx], pa[nx][kx], t, c[nx], l=1, r, a[nx], b[nx], ans, lvl[nx]; vector<int> d[nx]; void dfs(int u, int p) { pa[u][0]=p; lvl[u]=lvl[p]+1; for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1]; in[u]=++t; for (auto v:d[u]) if (v!=p) dfs(v, u); out[u]=t; } struct segtree { int d[4*nx]; void update(int l, int r, int i, int idx, int vl) { if (idx<l||r<idx) return; if (l==r) return d[i]+=vl, void(); int md=(l+r)/2; update(l, md, 2*i, idx, vl); update(md+1, r, 2*i+1, idx, vl); d[i]=d[2*i]+d[2*i+1]; } int query(int l, int r, int i, int ql, int qr) { if (qr<l||r<ql) return 0; if (ql<=l&&r<=qr) return d[i]; int md=(l+r)/2; return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr); } } s; int getlca(int u, int cur) { if (s.query(1, n, 1, in[u], out[u])==cur) return u; for (int i=kx-1; i>=0; i--) if (s.query(1, n, 1, in[pa[u][i]], out[pa[u][i]])!=cur) u=pa[u][i]; return pa[u][0]; } void add(int u) { if (l==r) return ans=1, s.update(1, n, 1, in[u], 1), void(); int v=u, lca=getlca(c[l], r-l); if (s.query(1, n, 1, in[u], out[u])>0) { if (lvl[lca]<=lvl[u]) return s.update(1, n, 1, in[u], 1), void(); ans+=lvl[lca]-lvl[u]; s.update(1, n, 1, in[u], 1); return; } for (int i=kx-1; i>=0; i--) if (s.query(1, n, 1, in[pa[v][i]], out[pa[v][i]])==0) v=pa[v][i]; v=pa[v][0]; if (lvl[lca]<=lvl[v]) ans+=lvl[u]-lvl[v], s.update(1, n, 1, in[u], 1); else ans+=lvl[u]-lvl[v]+lvl[pa[lca][0]]-lvl[v]+1, s.update(1, n, 1, in[u], 1); } void rem(int u) { s.update(1, n, 1, in[u], -1); int v=u, lca=getlca(c[l], r-l+1); if (s.query(1, n, 1, in[u], out[u])>0) { if (lvl[lca]<=lvl[u]) return; ans-=lvl[lca]-lvl[u]; return; } for (int i=kx-1; i>=0; i--) if (s.query(1, n, 1, in[pa[v][i]], out[pa[v][i]])==0) v=pa[v][i]; v=pa[v][0]; if (lvl[lca]<=lvl[v]) ans-=lvl[u]-lvl[v]; else ans-=lvl[u]-lvl[v]+lvl[pa[lca][0]]-lvl[v]+1; } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>m>>q; for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u); dfs(1, 1); for (int i=1; i<=m; i++) cin>>c[i]; for (int i=1; i<=q; i++) { cin>>a[i]>>b[i]; while (r<b[i]) add(c[++r]); //cout<<l<<' '<<r<<' '<<ans<<'\n'; while (l<a[i]) rem(c[l++]); //cout<<l<<' '<<r<<' '<<ans<<'\n'; cout<<ans<<'\n'; } } /* 7 6 6 1 2 1 3 2 4 2 5 3 6 3 7 2 3 6 4 5 7 1 1 2 2 3 3 4 4 5 5 6 6 */
#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...