제출 #1119259

#제출 시각아이디문제언어결과실행 시간메모리
1119259MrAndriaTourism (JOI23_tourism)C++14
28 / 100
5092 ms22592 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back //#define int long long int n,k,u,v,tin[200005],m,num[200005],val[200005],l,r,ans[200005],a[200005],sz,timer=0,dst[200005],lg,up[200005][25],tout[200005],q; pair <pair <int,int> ,int> query[200005]; vector <int> adj[100005]; set <int> s; void dfs(int x,int p,int ds){ tin[x]=timer++; val[tin[x]]=x; dst[x]=ds; up[x][0]=p; for (int i = 1; i <= lg; ++i) up[x][i] = up[up[x][i-1]][i-1]; for(int u=0;u<adj[x].size();u++){ if(adj[x][u]!=p){ dfs(adj[x][u],x,ds+1); } } tout[x] = timer++; } bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int lca(int u, int v) { if (is_ancestor(u, v)) return u; if (is_ancestor(v, u)) return v; for (int i = lg; i >= 0; --i) { if (!is_ancestor(up[u][i], v)) u = up[u][i]; } return up[u][0]; } int dist(int x,int y){ return dst[x]+dst[y]-2*dst[lca(x,y)]; } inline void add(int x){ // cout<<x<<"-"<<tin[x]<<endl; num[x]++; if(num[x]>1){ return; } if(s.size()==0){ s.insert(tin[x]); sz=0; return; } s.insert(tin[x]); set <int> :: iterator it=s.lower_bound(tin[x]); set <int> :: iterator it1=it; set <int> :: iterator it2=it; if(it1==s.begin()){ it1=s.end(); } it1--; it2++; if(it2==s.end()){ it2=s.begin(); } // cout<<(*it1)<<" "<<(*it)<<" "<<(*it2)<<" "<<val[(*it1)]<<" "<<val[(*it)]<<" "<<val[(*it2)]<<" "<<s.size()<<" "<<dist(val[(*it1)],val[(*it)])<<" "<<dist(val[(*it)],val[(*it2)])<<" "<<dist(val[(*it1)],val[(*it2)])<<" add\n"; sz+=(dist(val[(*it1)],val[(*it)])+dist(val[(*it)],val[(*it2)])-dist(val[(*it1)],val[(*it2)])); // cout<<" "<<sz<<endl; } inline void remove(int x){ num[x]--; if(num[x]>0){ return; } set <int> :: iterator it=s.lower_bound(tin[x]); if(s.size()==1){ s.erase(it); // cout<<s.size()<<endl; sz=0; return; } set <int> :: iterator it1=it; set <int> :: iterator it2=it; if(it1==s.begin()){ it1=s.end(); } it1--; it2++; if(it2==s.end()){ it2=s.begin(); } // cout<<(*it1)<<" "<<(*it)<<" "<<(*it2)<<" "<<val[(*it1)]<<" "<<val[(*it)]<<" "<<val[(*it2)]<<" "<<s.size()<<" "<<dist(val[(*it1)],val[(*it)])<<" "<<dist(val[(*it)],val[(*it2)])<<" "<<dist(val[(*it1)],val[(*it2)])<<" remove"; sz-=(dist(val[(*it1)],val[(*it)])+dist(val[(*it)],val[(*it2)])-dist(val[(*it1)],val[(*it2)])); s.erase(it); // cout<<" "<<sz<<endl; } bool comp(pair <pair <int,int>,int> a, pair <pair <int,int> ,int > b){ if(a.ff.ff/k ==b.ff.ff/k){ return a.ff.ss<b.ff.ss; } return (a.ff.ff)/k < (b.ff.ff)/k; } int main(){ scanf("%d%d%d",&n,&m,&q); lg=ceil(log2(n)); k=ceil(sqrt(m)); for(int i=1;i<=n-1;i++){ scanf("%d%d",&u,&v); adj[u].pb(v); adj[v].pb(u); } for(int i=1;i<=m;i++){ scanf("%d",&a[i]); } for(int i=1;i<=q;i++){ scanf("%d%d",&query[i].ff.ff,&query[i].ff.ss); query[i].ss=i; } dfs(1,1,0); sort(query+1,query+q+1,comp); int tl=1; int tr=1; int l,r; add(a[tl]); for(int i=1;i<=q;i++){ l=query[i].ff.ff; r=query[i].ff.ss; while(tr<r){ tr++; add(a[tr]); } while(l<tl){ tl--; add(a[tl]); } while(r<tr){ remove(a[tr]); tr--; } while(tl<l){ remove(a[tl]); tl++; } ans[query[i].ss]=(sz/2)+1; } for(int i=1;i<=q;i++){ printf("%d ",ans[i]); } }

컴파일 시 표준 에러 (stderr) 메시지

tourism.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
tourism.cpp: In function 'void dfs(int, int, int)':
tourism.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int u=0;u<adj[x].size();u++){
      |                 ~^~~~~~~~~~~~~~
tourism.cpp: In function 'int main()':
tourism.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
tourism.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
tourism.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
tourism.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         scanf("%d%d",&query[i].ff.ff,&query[i].ff.ss);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...