Submission #162257

#	Time	Username	Problem	Language	Result	Execution time	Memory
162257		Nordway	Dreaming (IOI13_dreaming)	C++14	100 / 100	196 ms	21368 KiB

dreaming

#include "dreaming.h"
 
#include <bits/stdc++.h>
 
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int inf=2e9;
const int MAXN=1e5+11;
 
vector<pii>g[MAXN];
 
struct Tree{
  int root,diam,u,v,rad;
}T[MAXN];
int par[MAXN],comp[MAXN],h[MAXN],d[MAXN];
int up[MAXN][20];
bool used[MAXN];
 
void addV(int v){
  up[v][0]=par[v];
  for(int i=1;i<=16;i++){
    up[v][i]=up[up[v][i-1]][i-1];
  }
}
 
int lca(int a,int b){
  if(h[a]<h[b])swap(a,b);
  int log;
  for(log=1;(1<<log)<=h[a];log++);
  log--;
  for(int i=log;i>=0;i--){
    if(h[a]-(1<<i)>=h[b]){
      a=up[a][i];
    }
  }
  if(a==b)return a;
  for(int i=log;i>=0;i--){
    if(up[a][i]!=0&&up[a][i]!=up[b][i]){
      a=up[a][i],b=up[b][i];
    }
  }
  return par[a];
}
 
void add(Tree &t,int b){
  int l=lca(t.u,b);
  int diam1=d[b]+d[t.u]-2*d[l];
  l=lca(t.v,b);
  int diam2=d[b]+d[t.v]-2*d[l];
  int diam3=t.diam;
  if(diam3>=diam1&&diam3>=diam2);
  else if(diam2>=diam1&&diam2>=diam3){
    t.diam=diam2;
    t.u=b;
  }
  else {
    t.diam=diam1;
    t.v=b;
  }
}
 
void bfs(int s){
  queue<int>q;
  q.push(s);
  used[s]=1;
  addV(s);
  d[s]=0;
  h[s]=0;
  while(!q.empty()){
    int v=q.front();
    q.pop();
    for(int i=0;i<sz(g[v]);i++){
      int to=g[v][i].x;
      if(!used[to]){
        par[to]=v;
        d[to]=d[v]+g[v][i].y;
        h[to]=h[v]+1;
        addV(to);
        add(T[comp[v]],to);
        q.push(to);
        used[to]=1;
        comp[to]=comp[v];
      }
    }
  }
}
 
int travelTime(int n,int M,int L,int a[],int b[],int t[]){
  for(int i=1;i<=n;i++){
    par[i]=0;
    comp[i]=i;
    T[i]=Tree{i,0,i,i,0};
  }
  for(int i=0;i<M;i++){
    g[a[i]+1].pb(mp(b[i]+1,t[i]));
    g[b[i]+1].pb(mp(a[i]+1,t[i]));
  }
  for(int i=1;i<=n;i++){
    if(!used[i]){
      bfs(i);
    }
  }
  for(int i=1;i<=n;i++){
    used[i]=0;
  }
  vector<pii>Comp;
  for(int i=1;i<=n;i++){
    if(!used[comp[i]]){
      int u=T[comp[i]].u;
      int v=T[comp[i]].v;
      int l=lca(u,v);
      vector<int>path1;
      vector<int>edg;
      while(u!=l){
        path1.pb(u);
        u=par[u];
      }
      vector<int>path2;
      while(v!=l){
        path2.pb(v);
        v=par[v];
      }
      path1.pb(l);
      while(!path2.empty()){
        path1.pb(path2.back());
        path2.pop_back();
      }
      int len=0;
      bool w=0;
      T[comp[i]].rad=inf;
      for(int j=0;j<sz(path1);j++){
        if(j>0){
          if(!w)len+=d[path1[j-1]]-d[path1[j]];
          else len+=d[path1[j]]-d[path1[j-1]];
        }
        if(path1[j]==l)w=1;
        int val=max(len,T[comp[i]].diam-len);
        if(val<T[comp[i]].rad){
          T[comp[i]].rad=val;
          T[comp[i]].root=path1[j];
        }
      }
      used[comp[i]]=1;
      Comp.pb(mp(T[comp[i]].rad,comp[i]));
    }
  }
  sort(all(Comp),greater<>());
  int ans=0;
  for(int i=0;i<sz(Comp);i++){
    ans=max(ans,T[Comp[i].y].diam);
  }
  if(sz(Comp)>1){
    if(ans<Comp[0].x+Comp[1].x+L){
      ans=Comp[0].x+Comp[1].x+L;
    }
    if(sz(Comp)>2){
      if(ans<Comp[1].x+Comp[2].x+2*L){
        ans=Comp[1].x+Comp[2].x+2*L;
      }
    }
  }
  return ans;
}
/*
int main(){
  int n,m,l;
  cin>>n>>m>>l;
  vector<int>a,b,t;
  for(int i=0;i<m;i++){
    int u,v,w;
    cin>>u>>v>>w;
    a.pb(u);
    b.pb(v);
    t.pb(w);
  }
  cout<<travelTime(n,m,l,a,b,t);
}*/

Compilation message (stderr)

dreaming.cpp: In function 'void bfs(int)':
dreaming.cpp:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<sz(g[v]);i++){
                  ^
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:141:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j=0;j<sz(path1);j++){
                    ^
dreaming.cpp:159:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<sz(Comp);i++){
                ^

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23