Submission #1278103

#TimeUsernameProblemLanguageResultExecution timeMemory
1278103sasdeTourism (JOI23_tourism)C++20
100 / 100
1066 ms50144 KiB
#include<bits/stdc++.h> using namespace std; #define sz(a) (int)a.size() #define all(x) x.begin(),x.end() #define ii pair<int,int> #define se second #define fi first #define emb emplace_back #define look_memory cerr<<'\n'<<abs(&M2-&M1)/1024.0/1024<<'\n' #define look_time cerr << "TIME : " << clock() * 0.001 << "s" <<'\n' const int N=3e5+5,inf=1e9,lim=2e5; int node,query,m,c[N]; ii b[N]; namespace sub456{ struct HLD { int n, curpos, curc; int bit[N]; vector<int> h,sl, up, curhead, curid, pos, posend, arr; vector<vector<int>> edge; HLD() : curpos(0), curc(0) {}; HLD(int _n) : n(_n), sl(n + 5), h(n + 5), up(n + 5), curhead(n + 5), curid(n + 5), pos(n + 5), posend(n+5), arr(n + 5), edge(n + 5) { curpos = curc = 0; }; void addedge(int u, int v) { edge[u].emplace_back(v); edge[v].emplace_back(u); } void update(int idx,int val){ // cout <<idx<<" "<<val<<'\n'; while(idx<=N-1){ bit[idx]+=val; idx+=idx&(-idx); } } int get(int idx){ int res=0; while(idx>0){ res+=bit[idx]; idx-=idx&(-idx); } return res; } int getrange(int l,int r){ // cout <<get(r)<<" "<<get(l-1)<<'\n'; return get(r)-get(l-1); } void dfs(int u, int cha) { sl[u] = 1; for (int v : edge[u]) { if (v == cha) continue; h[v] = h[u] + 1; up[v] = u; dfs(v, u); sl[u] += sl[v]; } } void hld(int u, int cha) { if (!curhead[curc]) curhead[curc] = u; curid[u] = curc; pos[u] = ++curpos; arr[curpos] = u; int nxt = 0; for (int v : edge[u]) { if (v != cha && sl[v] > sl[nxt]) nxt = v; } if (nxt) hld(nxt, u); for (int v : edge[u]) { if (v != cha && v != nxt) { ++curc; hld(v, u); } } posend[u]=curpos; } void build(int goc){ dfs(goc,-1); hld(goc,-1); } set<array<int,3>>s; void doi(int l,int r,int x){ while(true){ auto it=s.lower_bound({l,-inf,-inf}); if(it==s.end())break; array<int,3>x=*it; int u=x[1]; int v=x[0]; int val=x[2]; if(r<u||l>v)break; s.erase(it); int len=min(r,v)-max(l,u)+1; // cout <<u<<" "<<v<<" "<<val<<" "<<len<<'\n'; update(val+1,-len); if(u<l)s.insert({l-1,u,val}); if(r<v)s.insert({v,r+1,val}); } update(x+1,r-l+1); s.insert({r,l,x}); } void change(int u,int v,int val){ for(;curid[u]!=curid[v];v=up[curhead[curid[v]]]){ if(h[curhead[curid[u]]]>h[curhead[curid[v]]])swap(u,v); doi(pos[curhead[curid[v]]],pos[v],val); } if(h[u]>h[v])swap(u,v); doi(pos[u],pos[v],val); } }; vector<ii>req[N]; int ans[N]; void solve(){ HLD hld(node); for(int i=1;i<node;++i){ hld.addedge(b[i].fi,b[i].se); } for(int i=1;i<=query;++i){ int l,r; cin >> l >>r; ans[i]=1; req[r].emb(l,i); } hld.build(1); for(int i=1;i<=m;++i){ if(i>1){ hld.change(c[i-1],c[i],i-1); } hld.change(c[i],c[i],i); for(auto x:req[i])ans[x.se]=hld.getrange(x.fi+1,m+1); } for(int i=1;i<=query;++i)cout << ans[i]<<"\n"; for(int i=1;i<=query;++i)cerr << ans[i]<<"\n"; } } main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define task "aws" if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin >> node>>m >> query; for(int i=1;i<node;++i){ int u,v; cin >> u >> v; b[i]={u,v}; } for(int i=1;i<=m;++i)cin >> c[i]; sub456::solve(); }

Compilation message (stderr)

tourism.cpp:141:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  141 | main()
      | ^~~~
tourism.cpp: In function 'int main()':
tourism.cpp:148:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:149:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...