Submission #471534

#TimeUsernameProblemLanguageResultExecution timeMemory
471534NicolaAbusaad2014Race (IOI11_race)C++14
0 / 100
15 ms31692 KiB
/** * Prof.Nicola **/ #include "race.h" #include <bits/stdc++.h> using namespace std; #define endl "\n" #define mp make_pair #define F first #define S second #define REP(i,l,r) for(long long i=(l);i<(r);i++) #define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--) const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1}; const long double pi=3.14159265359; const long long mod=1e9+7; long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;} long long squared(long long x){return (x*x)%mod;} long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));} long long inv(long long x){return power(x,mod-2);} template<class T>void re(T&x){cin>>x;} template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);} template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}} template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}} template<class T>void out(T x){cout<<x<<" ";} template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;} template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;} template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;} template<class T>void out(set<T>x){while(!x.empty()){out(*x.begin());x.erase(*x.begin());}cout<<endl;} template<class T1,class T2>void out(map<T1,T2>x){while(!x.empty()){out(*x.begin());x.erase(x.begin()->first);}cout<<endl;} template<class T>void out(queue<T>x){while(!x.empty()){out(x.front());x.pop();}cout<<endl;} template<class T>void out(priority_queue<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;} template<class T>void out(stack<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;} template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();} template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();} set<long long>::iterator T; long long vLE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<=x){l+=z;}z/=2;}return l;} long long vL(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<x){l+=z;}z/=2;}return l;} long long vGE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return l;}l=vL(x,VT,l,r);if(l==r){return -1;}return l+1;} long long vG(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return l;}l=vLE(x,VT,l,r);if(l==r){return -1;}return l+1;} long long sLE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.begin()>x){return -1;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;} long long sL(long long x,set<long long>&ST){if(*ST.begin()>=x){return -1;}if(ST.count(x)){T=ST.find(x);T--;return *T;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;} long long sGE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.rbegin()<x){return -1;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;} long long sG(long long x,set<long long>&ST){if(*ST.rbegin()<=x){return -1;}if(ST.count(x)){T=ST.find(x);T++;return *T;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;} struct segment_tree { vector<long long>tree; long long operation(long long x,long long z) { return x+z; } void build(vector<long long>v) { tree.clear(); long long x=v.size(); while(x&(x-1)){ x=x&(x-1); } if(v.size()!=x){ x*=2; } tree.resize(x*2); tree[0]=x; for(long i=0;i<v.size();i++){ tree[i+x]=v[i]; } for(long i=x-1;i>0;i--){ tree[i]=operation(tree[i*2],tree[(i*2)+1]); } } long long get(long long l,long long r) { l+=tree[0]; r+=tree[0]; long long ans=0; while(l<=r){ if(l%2==1){ ans=operation(ans,tree[l]); } if(r%2==0){ ans=operation(ans,tree[r]); } l++; l/=2; r--; r/=2; } return ans; } void update(long long x,long long z) { x+=tree[0]; tree[x]=z; x/=2; while(x>0){ tree[x]=operation(tree[x*2],tree[(x*2)+1]); x/=2; } } }; long k,ans=1e9; vector<long>len; vector<pair<pair<long,long>,pair<long,long> > >mn(1e6+1); struct tree { long long n,counter; vector<vector<pair<long,long> > >edges; vector<vector<long> >parent; vector<pair<long,long> >sub; vector<long>depth,sz,val,rep,to,subtree,path; vector<bool>vis; segment_tree HLD; void scan0(long x,long p,long long l) { len[x]=l; depth[x]=depth[p]+1; parent[x][0]=p; sz[x]=1; counter++; sub[x].first=counter; REP(i,0,edges[x].size()){ if(edges[x][i].F==p||vis[edges[x][i].F]){ continue; } scan0(edges[x][i].F,x,l+edges[x][i].S); sz[x]+=sz[edges[x][i].F]; } sub[x].second=counter; } void scan(long x,long p,long long l,long h) { len[x]=l; depth[x]=depth[p]+1; if(l<=k){ if(depth[x]<mn[l].F.F){ if(mn[l].F.S==h){ mn[l].F.F=depth[x]; } else{ mn[l].S=mn[l].F; mn[l].F=mp(depth[x],h); } } else if(depth[x]<mn[l].F.S){ if(mn[l].F.S!=h){ mn[l].S=mp(depth[x],h); } } } parent[x][0]=p; sz[x]=1; counter++; sub[x].first=counter; REP(i,0,edges[x].size()){ if(edges[x][i].F==p||vis[edges[x][i].F]){ continue; } scan(edges[x][i].F,x,l+edges[x][i].S,h); sz[x]+=sz[edges[x][i].F]; } sub[x].second=counter; } void scan2(long x,long p,long long l,long h) { if(l>k){ return; } if(h==mn[k-l].F.S&&mn[k-l].S.S!=0){ ans=min(ans,depth[x]+mn[k-l].S.F); } else if(h!=mn[k-l].F.S){ ans=min(ans,depth[l]+mn[k-l].F.F); } sub[x].first=counter; REP(i,0,edges[x].size()){ if(edges[x][i].F==p||vis[edges[x][i].F]){ continue; } scan2(edges[x][i].F,x,l+edges[x][i].S,h); sz[x]+=sz[edges[x][i].F]; } sub[x].second=counter; } void scan3(long x,long p,long long l,long h) { mn[l]=mp(mp(0,0),mp(0,0)); sub[x].first=counter; REP(i,0,edges[x].size()){ if(edges[x][i].F==p||vis[edges[x][i].F]){ continue; } scan3(edges[x][i].F,x,l+edges[x][i].S,h); sz[x]+=sz[edges[x][i].F]; } sub[x].second=counter; } long long operation(long long x,long long z) { return max(x,z); } void up(long x,long z) { bool ok=false; to[x]=z; REP(i,0,edges[x].size()){ if(edges[x][i].F==parent[x][0]){ continue; } if(sz[edges[x][i].F]>=(sz[x]+1)/2){ up(edges[x][i].F,z); ok=true; continue; } up(edges[x][i].F,edges[x][i].F); } if(!ok){ long node=x; while(depth[node]>=depth[to[x]]){ rep[node]=counter; counter++; node=parent[node][0]; } } } long long decompose(long x,long z) { if(rep[to[x]]-rep[x]>=z){ return HLD.get(rep[x],rep[x]+z); } return operation(HLD.get(rep[x],rep[to[x]]),decompose(parent[to[x]][0],z-1-(rep[to[x]]-rep[x]))); } long centroid(long x,long p,long z) { long mx=0,node=x; REP(i,0,edges[x].size()){ if(!vis[edges[x][i].F]&&edges[x][i].F!=p&&sz[edges[x][i].F]>mx){ mx=sz[edges[x][i].F]; node=edges[x][i].F; } } if(mx<z){ return x; } return centroid(node,x,z); } void read(long nodes,vector<vector<pair<long,long> > >e) { n=nodes; edges=e; val.clear(); val.resize(n+1); } void build(long long root=1) { counter=-1; vis.clear(); vis.resize(n+1); depth.clear(); depth.resize(n+1); depth[0]=-1; sz.clear(); sz.resize(n+1); rep.clear(); rep.resize(n+1); to.clear(); to.resize(n+1); sub.clear(); sub.resize(n+1); parent.clear(); parent.resize(n+1); REP(i,0,n+1){ parent[i].resize(21); } scan(root,0,0,1); subtree.clear(); subtree.resize(n); REP(i,1,n+1){ subtree[sub[i].first]=val[i]; } REP(i,1,21){ REP(j,1,n+1){ parent[j][i]=parent[parent[j][i-1]][i-1]; } } counter=0; up(root,root); path.clear(); path.resize(n); REP(i,1,n+1){ path[rep[i]]=val[i]; } } long lift(long x,long z) { if(z<=0){ return x; } pair<long,long long>p; p.first=0; p.second=1; long d=z; while(d>1){ d/=2; p.first++; p.second*=2; } while(z>0){ if(z>=p.second){ z-=p.second; x=parent[x][p.first]; } p.first--; p.second/=2; } return x; } long LCA(long x,long z) { long p=0,d=depth[x]-depth[z]; x=lift(x,d); z=lift(z,-d); if(x==z){ return x; } d=depth[x]; while(d>1){ d/=2; p++; } while(p>=0){ if(parent[x][p]!=parent[z][p]){ x=parent[x][p]; z=parent[z][p]; } p--; } x=parent[x][0]; return x; } }; tree t; void solve(long x) { t.scan0(x,0,0); x=t.centroid(x,0,(t.sz[x]+1)/2); t.vis[x]=true; REP(i,0,t.edges[x].size()){ if(t.vis[t.edges[x][i].F]){ continue; } t.scan(t.edges[x][i].F,0,0,t.edges[x][i].F); } REP(i,0,t.edges[x].size()){ if(t.vis[t.edges[x][i].F]){ continue; } t.scan2(t.edges[x][i].F,0,0,t.edges[x][i].F); } REP(i,0,t.edges[x].size()){ if(t.vis[t.edges[x][i].F]){ continue; } t.scan3(t.edges[x][i].F,0,0,t.edges[x][i].F); } REP(i,0,t.edges[x].size()){ if(t.vis[t.edges[x][i].F]){ continue; } solve(t.edges[x][i].F); } } int best_path(int N, int K, int H[][2], int L[]) { k=K; len.resize(N+1); vector<vector<pair<long,long> > >e(N+1); REP(i,0,N-1){ e[H[i][0]].push_back(mp(H[i][1],L[i])); e[H[i][1]].push_back(mp(H[i][0],L[i])); } t.read(N,e); t.build(); return N; }

Compilation message (stderr)

race.cpp: In member function 'void segment_tree::build(std::vector<long long int>)':
race.cpp:59:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   59 |         if(v.size()!=x){
      |            ~~~~~~~~^~~
race.cpp:64:23: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(long i=0;i<v.size();i++){
      |                      ~^~~~~~~~~
race.cpp: In member function 'void tree::scan0(long int, long int, long long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:121:9: note: in expansion of macro 'REP'
  121 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'void tree::scan(long int, long int, long long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:154:9: note: in expansion of macro 'REP'
  154 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'void tree::scan2(long int, long int, long long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:175:9: note: in expansion of macro 'REP'
  175 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'void tree::scan3(long int, long int, long long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:188:9: note: in expansion of macro 'REP'
  188 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'void tree::up(long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:205:9: note: in expansion of macro 'REP'
  205 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In member function 'long int tree::centroid(long int, long int, long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:235:9: note: in expansion of macro 'REP'
  235 |         REP(i,0,edges[x].size()){
      |         ^~~
race.cpp: In function 'void solve(long int)':
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:347:5: note: in expansion of macro 'REP'
  347 |     REP(i,0,t.edges[x].size()){
      |     ^~~
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:353:5: note: in expansion of macro 'REP'
  353 |     REP(i,0,t.edges[x].size()){
      |     ^~~
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:359:5: note: in expansion of macro 'REP'
  359 |     REP(i,0,t.edges[x].size()){
      |     ^~~
race.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
race.cpp:365:5: note: in expansion of macro 'REP'
  365 |     REP(i,0,t.edges[x].size()){
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...