Submission #405662

#	Time	Username	Problem	Language	Result	Execution time	Memory
405662		Alex_tz307	Dreaming (IOI13_dreaming)	C++17	100 / 100	107 ms	17784 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define INF 0x3f3f3f3f
 
using namespace std;
 
const int MAXN = 1e5;
vector<pair<int,int>> G[MAXN];
int p[MAXN], dp1[MAXN], dp2[MAXN], node, val, dp[MAXN], best_node, best_dist;
bitset<MAXN> viz;
vector<int> nodes;
 
void max_self(int &a, int b) {
  a = max(a, b);
}
 
void dfs1(int u) {
  viz[u] = true;
  for (auto v : G[u])
    if (!viz[v.first]) {
      p[v.first] = u;
      dfs1(v.first);
      if (dp1[u] <= dp1[v.first] + v.second) {
        dp2[u] = dp1[u];
        dp1[u] = dp1[v.first] + v.second;
      } else max_self(dp2[u], dp1[v.first] + v.second);
    }
}
 
void dfs2(int u, int dist) {
  dp[u] = max(dp1[u], dist);
  if (dp[u] < val) {
    val = dp[u];
    node = u;
  }
  for (auto v : G[u])
    if (v.first != p[u]) {
      if (dp1[u] == dp1[v.first] + v.second)
        dfs2(v.first, max(dp2[u], dist) + v.second);
      else dfs2(v.first, max(dp1[u], dist) + v.second);
    }
}
 
void find_diameter(int u, int parent, int dist) {
  if (best_dist < dist) {
    best_dist = dist;
    best_node = u;
  }
  for (auto v : G[u])
    if (v.first != parent)
      find_diameter(v.first, u, dist + v.second);
}
 
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  for (int i = 0; i < M; ++i) {
    int u = A[i], v = B[i], w = T[i];
    G[u].emplace_back(v, w);
    G[v].emplace_back(u, w);
  }
  int max_val = -1, u = -1;
  for (int i = 0; i < N; ++i)
    if (!viz[i]) {
      p[i] = -1;
      dfs1(i);
      node = -1;
      val = INF;
      dfs2(i, 0);
      nodes.emplace_back(node);
      if (max_val < dp[node]) {
        max_val = dp[node];
        u = node;
      }
    }
  for (int v : nodes)
    if (u != v) {
      G[u].emplace_back(v, L);
      G[v].emplace_back(u, L);
    }
  best_node = best_dist = -1;
  find_diameter(0, -1, 0);
  best_dist = -1;
  find_diameter(best_node, -1, 0);
  return best_dist;
}

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