Submission #142845

#	Time	Username	Problem	Language	Result	Execution time	Memory
142845		Milki	Dreaming (IOI13_dreaming)	C++14	54 / 100	109 ms	15572 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], dist[MAXN], dep[MAXN];
point par[MAXN], mx[MAXN];

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);
  }
}

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

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

  point ret = point(0, 0);
  while(!Q.empty()){
    int 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));
  int Time = 0;
  REP(i, N)
    if(boja[i] == -1)
      color(i, Time ++);

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

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

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

    deque<point> lt, rt;

    while(dep[a] != dep[b]){
      lt.push_back(par[a]);
      a = par[a].first;
    }

    while(a != b){
      lt.push_back(par[a]);
      a = par[a].first;

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

    int sum = 0;
    for(auto it : lt){
      sum += it.second;
      mx[i] = min(mx[i], point(max(d - sum, sum), it.first));
    }
    for(auto it : rt){
      sum += it.second;
      mx[i] = min(mx[i], point(max(d - sum, sum), it.first));
    }

    //mx[i] = max(mx[i], find_furthest(i, mx[i].second));
  }

  sort(mx, mx + Time, greater<point>());
  //TRACE(mx[0].first); TRACE(mx[1].first); TRACE(L);

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

//#endif // DREAMING_H_INCLUDED

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