Submission #1139781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139781		fryingduc	Dreaming (IOI13_dreaming)	C++20	100 / 100	72 ms	18248 KiB

dreaming

#include "bits/stdc++.h"
#include "dreaming.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)
#endif  

const int maxn = 1e5 + 5;
const int inf = 2e9;
int n, m, l;
int dep[maxn];
vector<pair<int, int>> g[maxn];
pair<int, int> f[maxn];
pair<int, int> opt[maxn];
bool vis[maxn];
int cdist;

void upd(pair<int, int> &ft, int x) {
  vector<int> a;
  a.push_back(ft.first);
  a.push_back(ft.second);
  a.push_back(x);
  sort(a.begin(), a.end());
  ft = make_pair(a[2], a[1]);
}

void pre_dfs(int u, int prev) {
  vis[u] = 1;
  f[u] = make_pair(0, -inf);
  for(auto e:g[u]) {
    int v = e.first, w = e.second;
    if(v == prev) continue;
    dep[v] = dep[u] + w;
    pre_dfs(v, u);
    upd(f[u], f[v].first + w);
  }
}

void reroot(int u, int prev) {
  opt[u] = f[u];
  if(cdist == -1 || f[cdist].first > f[u].first) {
    cdist = u;
  }
  for(auto e:g[u]) {
    int v = e.first, w = e.second;
    if(v == prev) continue;
    pair<int, int> mem = f[v];
    if(f[u].first == f[v].first + w) {
      upd(f[v], f[u].second + w);
    } else {
      upd(f[v], f[u].first + w);
    }
    reroot(v, u);
    f[v] = mem;
  }
}

int find_center(int root) {
  dep[root] = 0;
  pre_dfs(root, 0);
  cdist = -1;
  reroot(root, 0);
  return cdist;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  n = N;
  m = M;
  l = L;
  if(n == 1) {
    return 0;
  }
  for(int i = 0; i < m; ++i) {
    int u = A[i], v = B[i], w = T[i];
    ++u, ++v;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  set<array<int, 3>> s;
  for(int i = 1; i <= n; ++i) {
    if(vis[i]) continue;
    pre_dfs(i, 0);
    int center = find_center(i);
    s.insert({opt[center].first, opt[center].second, center});
  }
  while((int)s.size() > 1) {
    array<int, 3> ft = *s.begin();
    s.erase(s.begin());
    array<int, 3> se = *s.rbegin();
    s.erase(--s.end());
    pair<int, int> cft = {-inf, -inf};
    upd(cft, ft[0]), upd(cft, ft[1]), upd(cft, se[0] + l);
//    upd(cft, se[1] + l);
    pair<int, int> cse = {-inf, -inf};
    upd(cse, ft[0] + l), upd(cse, se[0]), upd(cse, se[1]);
//    upd(cse, ft[1] + l);
//    debug(cft, cse, ft, se);
    if(cft < cse) {
      s.insert({cft.first, cft.second, ft[2]});
    } else {
      s.insert({cse.first, cse.second, se[2]});
    }
  }
  array<int, 3> ft = *s.begin();
  return ft[0] + ft[1];
} 

#ifdef duc_debug
signed main() {
  cin >> n >> m >> l;
  int a[m], b[m], t[m];
  for(int i = 0; i < m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    a[i] = u, b[i] = v, t[i] = w;
  }
  cout << travelTime(n, m, l, a, b, t);
}
#endif
/*
11 8 3
0 1 3
1 2 1
0 3 2
4 5 4
4 6 2
7 8 7
7 9 4
8 10 5

7 5 3
0 1 3
1 2 1
0 3 2
4 5 4
4 6 2

*/

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