Submission #1260366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260366		repmann	Dreaming (IOI13_dreaming)	C++20	0 / 100	37 ms	10816 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int N, M, L;
int DP[2][100001];
vector <pair <int, int>> VG[100001];
inline int DFS(int node, int parent = 0)
{
  int ret = node;
  for(pair <int, int> p : VG[node])
  {
    if(p.second == parent) continue;
    DP[0][p.second] = DP[0][node] + p.first;
    int temp = DFS(p.second, node);
    if(DP[0][temp] > DP[0][ret]) ret = temp;
  }
  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);
  DP[0][u] = 0;
  int v = DFS(u);
  swap(*DP[0], *DP[1]);
  int diameter = DP[0][DFS(v)];
  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 n, m, l, u[100001], v[100001], w[100001];
//int main()
//{
////  cin >> n >> m >> l;
////  for(int i = 0; i < m; i++) cin >> u[i] >> v[i] >> w[i];
//  n = 100000;
//  m = n >> 1;
//  l = 10000;
//  for(int i = 0; i < m; i++)
//  {
//    u[i] = (i << 1);
//    v[i] = (i << 1) + 1;
//    w[i] = 10000;
//  }
//  cout << travelTime(n, m, l, u, v, w) << '\n';
//
//  return 0;
//}

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