제출 #231267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231267		quocnguyen1012	Dreaming (IOI13_dreaming)	C++14	100 / 100	125 ms	14200 KiB

dreaming

#ifndef LOCAL
#include "dreaming.h"
#endif // LOCAL
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

vector<ii> adj[maxn];
int w[maxn], par[maxn];
int far = 0;
bool vis[maxn];
int high[maxn], mid[maxn];

void dfs(int u, int p = -1)
{
  vis[u] = true;
  par[u] = p;
  if(w[far] < w[u]) far = u;
  for(auto & v : adj[u]) if(v.fi != p){
    w[v.fi] = w[u] + v.se;
    dfs(v.fi, u);
  }
}

void dia(int u)
{
  far = u;
  w[u] = 0; dfs(u);
  w[far] = 0;
  dfs(far);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  for(int i = 0; i < M; ++i){
    adj[A[i]].eb(B[i], T[i]);
    adj[B[i]].eb(A[i], T[i]);
  }
  int cc = 0;
  for(int i = 0; i < N; ++i) if(!vis[i]){
    ++cc;
    dia(i); high[cc] = w[far];
    mid[cc] = far;
    for(int v = far; par[v] != -1; v = par[v]){
      if(high[cc] > max(w[v], w[far] - w[v])){
        mid[cc] = v;
        high[cc] = max(w[v], w[far] - w[v]);
      }
    }
  }
  int r = -1;
  for(int i = 1; i <= cc; ++i){
    if(r == -1 || high[r] < high[i]) r = i;
  }
  for(int i = 1; i <= cc; ++i) if(r != i){
    adj[mid[r]].eb(mid[i], L);
    adj[mid[i]].eb(mid[r], L);
  }
  dia(0);
  return w[far];
}

#ifdef LOCAL
signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  int N, M, L;
  cin >> N >> M >> L;
  int A[M], B[M], T[M];
  for(int i = 0; i < M; ++i)
    cin >> A[i];
  for(int i = 0; i < M; ++i)
    cin >> B[i];
  for(int i = 0; i < M; ++i)
    cin >> T[i];
  cout << travelTime(N, M, L, A, B, T);
}
#endif // LOCAL

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