Submission #1260361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260361		repmann	Dreaming (IOI13_dreaming)	C++20	59 / 100	1096 ms	41068 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int N, M, L;
int DP[2][1000001];
vector <pair <int, int>> VG[1000001];
inline pair <int, int> DFS(int node, int parent = 0)
{
  pair <int, int> ret = {DP[0][node], node};
  for(pair <int, int> p : VG[node])
  {
    if(p.second == parent) continue;
    DP[0][p.second] = DP[0][node] + p.first;
    ret = max(DFS(p.second, node), ret);
  }
  return ret;
}
inline int MDFS(int node, int parent = 0)
{
  int ret = max(DP[0][node], DP[1][node]);
  for(pair <int, int> p : VG[node]) if(p.second != parent) ret = min(MDFS(p.second, node), ret);
  return ret;
}
inline pair <int, int> Diameter(int node)
{
  int u = DFS(node).second;
  DP[0][u] = 0;
  int v = DFS(u).second;
  swap(DP[0], DP[1]);
  int diameter = DFS(v).first;
  int minimum = MDFS(v);
  return {diameter, minimum};
}
int travelTime(int n, int m, int l, int u[], int v[], int w[])
{
  N = n;
  M = m;
  L = l;
  for(int i = 0; i < M; i++)
  {
    VG[u[i] + 1].push_back({w[i], v[i] + 1});
    VG[v[i] + 1].push_back({w[i], u[i] + 1});
  }
  int diameter = 0, maximum[3];
  maximum[0] = maximum[1] = maximum[2] = 0;
  for(int i = 1; i <= N; i++)
  {
    if(DP[0][i] || DP[1][i] || !VG[i].size()) continue;
//    cout << i << ":\n";
    pair <int, int> temp = Diameter(i);
    if(!temp.first) continue;
//    cout << temp.first << ' ' << temp.second << '\n';
    diameter = max(temp.first, diameter);
    for(int j = 0; j < 3; j++)
    {
      if(temp.second <= maximum[j]) continue;
      for(int k = 2; k > j; k--) maximum[k] = maximum[k - 1];
      maximum[j] = temp.second;
      break;
    }
  }
//  cout << "maximum:\n";
//  for(int j = 0; j < 3; j++) cout << maximum[j] << " \n"[j == 2];
  if(M == (N - 1)) return diameter;
  if(M == (N - 2)) return max(diameter, maximum[0] + maximum[1] + L);
  return max({diameter, maximum[0] + maximum[1] + L, maximum[1] + maximum[2] + L + L});
}
//int main()
//{
//  int n, m, l, u[100], v[100], w[100];
//  cin >> n >> m >> l;
//  for(int i = 0; i < m; i++) cin >> u[i] >> v[i] >> w[i];
//  cout << travelTime(n, m, l, u, v, w) << '\n';
//
//  return 0;
//}

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