Submission #1283542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283542		DeltaStruct	Dreaming (IOI13_dreaming)	C++20	0 / 100	35 ms	12888 KiB

dreaming

#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"

int travelTime(int n,int m,int q,int EA[],int EB[],int ET[]){
  vector<vector<pair<int,int>>> G(n); for (int i(0);i < m;++i){
    G[EA[i]].emplace_back(EB[i],ET[i]),G[EB[i]].emplace_back(EA[i],ET[i]);
  }
  vector<int> dist0(n),dist1(n),A,vis(n,1);
  auto dfs0 = [&](auto& dfs,int x,int p,int d) -> pair<int,int> {
    pair<int,int> ret(d,x);
    A.emplace_back(x),vis[x] = 0;
    for (auto [y,z]:G[x]) if (y!=p) ret = max(ret,dfs(dfs,y,x,d+z));
    return ret;
  };
  auto dfs1 = [&](auto& dfs,int x,int p,int d,vector<int>& dist) -> pair<int,int> {
    pair<int,int> ret(d,x); dist[x] = d;
    for (auto [y,z]:G[x]) if (y!=p) ret = max(ret,dfs(dfs,y,x,d+z,dist));
    return ret;
  };
  vector<int> R;
  for (int i(0);i < n;++i) if (vis[i]){
    int x = dfs0(dfs0,i,-1,0).second,y = dfs1(dfs1,x,-1,0,dist0).second;
    dfs1(dfs1,y,-1,0,dist1);
    R.emplace_back(1e9);
    for (int k:A) R.back() = min(R.back(),max(dist0[k],dist1[k]));
    A.clear();
  }
  sort(R.begin(),R.end(),greater<int>());
  return R[0]+(R.size()==1?0:R[1]+q);
}

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