Submission #940242

#	Time	Username	Problem	Language	Result	Execution time	Memory
940242		shenfe1	Dreaming (IOI13_dreaming)	C++17	47 / 100	180 ms	22228 KiB

dreaming

#include <bits/stdc++.h>

#pragma optimize("Ofast")
#pragma target("avx2")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
// #define int ll

const int MAX=1e5+15;
const ll inf=1e9;  
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;

int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1);
  int k=binpow(a,n/2);
  return k*k;
}

#include "dreaming.h"

int n;
int tin[MAX],tout[MAX],timer;
int use[MAX];
int d[MAX];
int rev[MAX];
vector<pii> g[MAX];
vector<int> vec;

void dfs1(int v){
  vec.pb(v);
  use[v]=1;
  for(auto to:g[v]){
    if(!use[to.F])dfs1(to.F);
  }
}

void dfs(int v,int p=-1){
  tin[v]=++timer;
  rev[timer]=v;
  for(auto to:g[v]){
    if(to.F!=p){
      d[to.F]=d[v]+to.S;
      dfs(to.F,v);
    }
  }
  tout[v]=timer;
}

int t[4*MAX],add[4*MAX];
int C;

void build(int v,int tl,int tr){
  add[v]=0;
  if(tl==tr){
    t[v]=d[rev[tl]];
    return;
  }
  int tm=(tl+tr)/2;
  build(2*v,tl,tm);
  build(2*v+1,tm+1,tr);
  t[v]=max(t[2*v],t[2*v+1]);
}

void push(int v){
  add[2*v]+=add[v];
  add[2*v+1]+=add[v];
  t[2*v]+=add[v];
  t[2*v+1]+=add[v];
  add[v]=0;
}

void update(int v,int tl,int tr,int l,int r,int x){
  if(l>r||tl>r||l>tr)return;
  if(l<=tl&&tr<=r){
    t[v]+=x;
    add[v]+=x;
    return;
  }
  int tm=(tl+tr)/2;
  push(v);
  update(2*v,tl,tm,l,r,x);
  update(2*v+1,tm+1,tr,l,r,x);
  t[v]=max(t[2*v],t[2*v+1]);
}

pii calc(int v,int p=-1){
  int ans=t[1];
  int ans1=t[1];
  // cout<<v<<" "<<t[1]<<"\n";
  for(auto to:g[v]){
    if(to.F==p)continue;
    update(1,1,C,tin[to.F],tout[to.F],-to.S);
    update(1,1,C,1,tin[to.F]-1,to.S);
    update(1,1,C,tout[to.F]+1,C,to.S);
    pii bf=calc(to.F,v);
    ans=max(ans,bf.F);
    ans1=min(ans1,bf.S);
    update(1,1,C,tin[to.F],tout[to.F],to.S);
    update(1,1,C,1,tin[to.F]-1,-to.S);
    update(1,1,C,tout[to.F]+1,C,-to.S);
  }
  // cout<<v<<" "<<ans<<" "<<t[1]<<"\n";
  return {ans,ans1};
}

pii solve(vector<int> ver){
  {
    timer=0;
    for(int i=1;i<=sz(ver);i++)rev[i]=0;
    for(int x:ver)d[x]=0;
    dfs(ver[0]);
  }
  C=sz(ver);
  build(1,1,C);
  pii res=calc(ver[0]);
  return res;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  assert(M==N-2);
  n=N;
  for(int i=0;i<M;i++){
    g[A[i]+1].pb({B[i]+1,T[i]});
    g[B[i]+1].pb({A[i]+1,T[i]});
  }
  int mxD=0;
  int ans=0;
  vector<int> dep;
  for(int i=1;i<=n;i++){
    if(!use[i]){
      dfs1(i);
      pii bf=solve(vec);
      dep.pb(bf.S);
      mxD=max(mxD,bf.F);
      vec.clear();
    }
  }
  if(sz(dep)>=2)ans=max(ans,dep.back()+dep[sz(dep)-2]+L);
  if(sz(dep)>=3)ans=max(ans,dep[sz(dep)-2]+dep[sz(dep)-3]+L);
  return max(mxD,ans);
}

Compilation message (stderr)

dreaming.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
dreaming.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |

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