Submission #142860

#	Time	Username	Problem	Language	Result	Execution time	Memory
142860		Milki	Dreaming (IOI13_dreaming)	C++14	100 / 100	135 ms	20444 KiB

dreaming

//#ifndef DREAMING_H_INCLUDED
//#define DREAMING_H_INCLUDED

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 1e5 + 5;

vector <point> E[MAXN];
vector <int> component[MAXN];
int boja[MAXN], dp_down[MAXN], dp_up[MAXN], sol;


void color(int x, int Time){
  boja[x] = Time;
  component[Time].pb(x);
  for(auto e : E[x]){
    if(boja[e.first] != -1) continue;
    color(e.first, Time);
  }
}

void dfs_down(int x, int p = -1){
  for(auto e : E[x]){
    if(e.first == p) continue;
    dfs_down(e.first, x);
    dp_down[x] = max(dp_down[x], dp_down[e.first] + e.second);
  }
}

void merge(point &a, int x){
  if(x > a.first){
    a.second = a.first;
    a.first = x;
  }
  else if(x > a.second)
    a.second = x;
}

void dfs_up(int x, int p = -1){
  point maxi = point(0, 0);

  for(auto e : E[x]){
    if(e.first == p) continue;
    merge(maxi, dp_down[e.first] + e.second);
  }

  for(auto e : E[x]){
    if(e.first == p) continue;
    if(maxi.first == dp_down[e.first] + e.second)
      dp_up[e.first] = maxi.second + e.second;
    else
      dp_up[e.first] = maxi.first + e.second;

    dp_up[e.first] = max(dp_up[e.first], dp_up[x] + e.second);
    dfs_up(e.first, x);
  }

  sol = max(sol, maxi.first + maxi.second);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  REP(i, M){
    E[ A[i] ].pb( point( B[i], T[i] ) );
    E[ B[i] ].pb( point( A[i], T[i] ) );
  }

  memset(boja, -1, sizeof(boja));
  int Time = 0;
  REP(i, N)
    if(boja[i] == -1)
      color(i, Time ++);

  vector<int> v;
  REP(i, Time){
    dfs_down(component[i][0]);
    dfs_up(component[i][0]);

    int mn = 1e9;
    for(auto it : component[i]){
      mn = min(mn, max(dp_down[it], dp_up[it]));
    }
    v.pb(mn);
  }

  sort(v.rbegin(), v.rend());

  if(Time == 1)
    return sol;
  else if(Time == 2)
    return max(sol, v[0] + v[1] + L);
  else
    return max(v[1] + v[2] + 2 * L, max(sol, v[0] + v[1] + L));
}

//#endif // DREAMING_H_INCLUDED

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