Submission #142839

#	Time	Username	Problem	Language	Result	Execution time	Memory
142839		Milki	Dreaming (IOI13_dreaming)	C++14	24 / 100	165 ms	18536 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<ll, ll> point;

const ll MAXN = 1e5 + 5;

vector <point> E[MAXN];
vector <ll> component[MAXN];
ll boja[MAXN], dist[MAXN], dep[MAXN], mx[MAXN];
point par[MAXN];

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

point find_furthest(ll cmp, ll x){
  for(auto it : component[cmp])
    dist[it] = 0;

  queue<ll> Q;
  Q.push(x);

  point ret = point(0, 0);
  while(!Q.empty()){
    ll nx = Q.front(); Q.pop();
    for(auto e : E[nx]){
      if(dist[e.first] || e.first == x)
        continue;

      par[e.first] = point(nx, e.second);
      dep[e.first] = dep[nx] + 1;
      dist[e.first] = dist[nx] + e.second;
      ret = max(ret, point(dist[e.first], e.first));
      Q.push(e.first);
    }
  }

  return ret;
}

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));
  ll Time = 0;
  REP(i, N)
    if(boja[i] == -1)
      color(i, Time ++);

  ll ret = 0;
  REP(i, Time){
    ll a = find_furthest(i, component[i][0]).second;
    point najdalji = find_furthest(i, a);
    ll b = najdalji.second, d = najdalji.first;

    if(dep[a] < dep[b])
      swap(a, b);

    ret = max(ret, d);
    mx[i] = d;

    ll sum = 0;
    while(dep[a] != dep[b]){
      sum += par[a].second;
      a = par[a].first;
      mx[i] = min(mx[i], max(d - sum, sum));
    }
    deque<ll> lt, rt;
    while(a != b){
      lt.push_back(par[a].second);
      a = par[a].first;

      rt.push_front(par[b].second);
      b = par[b].first;
    }

    for(auto it : lt){
      sum += it;
      mx[i] = min(mx[i], max(d - sum, sum));
    }
    for(auto it : rt){
      sum += it;
      mx[i] = min(mx[i], max(d - sum, sum));
    }
  }

  sort(mx, mx + Time, greater<ll>());

  if(Time == 1)
    return ret;
  else
    return max(ret, mx[0] + mx[1] + L);
}

//#endif // DREAMING_H_INCLUDED

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