Submission #895917

#TimeUsernameProblemLanguageResultExecution timeMemory
895917Tuanlinh123Tourism (JOI23_tourism)C++17
0 / 100
187 ms16344 KiB
#include<bits/stdc++.h> #define ll long long #define pll pair<ll, ll> #define pb push_back #define mp make_pair #define fi first #define se second #define ld long double using namespace std; const ll maxn=100005; vector <ll> A[maxn]; vector <pll> L[maxn]; ll n, m, q, St[maxn*4], bit[maxn], c[maxn], ans[maxn]; ll Time, tin[maxn], h[maxn], pa[maxn], dep[maxn], child[maxn], big[maxn]; void update(ll i, ll val) { // cout << i << " " << val << "\n"; for (; i<=n; i+=i&(-i)) bit[i]+=val; } ll query(ll l, ll r) { ll ans=0; l--; for (; r; r-=r&(-r)) ans+=bit[r]; for (; l; l-=l&(-l)) ans-=bit[l]; return ans; } void update(ll i, ll Start, ll End, ll l, ll r, ll val) { if (Start>r || End<l) return; // cout << i << " " << St[i] << " " << Start << " " << End << " " << l << " " << r << " " << val << "\n"; if (Start>=l && End<=r && St[i]!=-1) { if (St[i]) update(St[i], -(End-Start+1)); update(val, End-Start+1); St[i]=val; return; } if (St[i]!=-1) St[i*2]=St[i*2+1]=St[i]; ll mid=(Start+End)/2; if (mid>=l) update(i*2, Start, mid, l, r, val); if (mid+1<=r) update(i*2+1, mid+1, End, l, r, val); if (St[i*2]==St[i*2+1]) St[i]=St[i*2]; else St[i]=-1; } void dfs(ll u) { child[u]=1; for (ll v:A[u]) if (v!=pa[u]) { dep[v]=dep[u]+1, pa[v]=u; dfs(v), child[u]+=child[v]; if (child[v]>child[big[u]]) big[u]=v; } } void dfs2(ll u) { tin[u]=++Time; if (u==big[pa[u]]) h[u]=h[pa[u]]; else h[u]=u; if (big[u]) dfs2(big[u]); for (ll v:A[u]) if (v!=pa[u] && v!=big[u]) dfs2(v); } void update(ll u, ll v, ll val) { for (; h[u]!=h[v]; u=pa[h[u]]) { if (dep[h[u]]<dep[h[v]]) swap(u, v); update(1, 1, n, tin[h[u]], tin[u], val); } if (dep[u]<dep[v]) swap(u, v); update(1, 1, n, tin[v], tin[u], val); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> q; for (ll i=1; i<n; i++) { ll u, v; cin >> u >> v; A[u].pb(v); A[v].pb(u); } dfs(1); dfs2(1); for (ll i=1; i<=m; i++) cin >> c[i]; for (ll i=1; i<=q; i++) { ll l, r; cin >> l >> r; L[r].pb({l, i}); } for (ll i=1; i<=m; i++) { if (i>1) update(c[i-1], c[i], i-1); update(c[i], c[i], i); for (auto &[l, idx]:L[i]) ans[idx]=query(l, i); } for (ll i=1; i<=q; i++) cout << ans[i] << "\n"; }
#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...