Submission #846689

#	Time	Username	Problem	Language	Result	Execution time	Memory
846689		Derek0	Dreaming (IOI13_dreaming)	C++17	100 / 100	75 ms	19396 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>

using namespace std;

#define overload4(a, b, c, d, name, ...) name
#define rep1(i, n) for(ll i = 0; i < (n); ++i)
#define rep2(i, a, b) for(ll i = (a); i < (b); ++i)
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define per1(i, n) for(ll i = (n) - 1; i >= 0; --i)
#define per2(i, a, b) for(ll i = (b) - 1; i >= a; --i)
#define per3(i, a, b, c) for(ll i = (b) - 1; i >= (a); i -= (c))
#define per(...) overload4(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)
#define pb emplace_back
#define lb(v,k) (ll) (lower_bound(all(v), (k)) - v.begin())
#define ub(v,k) (ll) (upper_bound(all(v), (k)) - v.begin())
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T, vector<T>, greater<T>>
typedef long long ll;
typedef pair<ll,ll> P;
using vi = vector<ll>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vvvvi = vector<vvvi>;
using vp = vector<P>;
using vvp = vector<vp>;

constexpr int _ = 100010;

ll vis[_], dist[_][3];
vp g[_];
vi s;

void dfs(ll v, ll p, ll t) {
  if (p == -1) s.clear(); 
  s.pb(v);
  for (auto [u, w] : g[v]) {
    if (u == p) continue;
    dist[u][t] = dist[v][t] + w;
    dfs(u, v, t);
  }
}

ll get(ll t) {
  ll x = -1;
  for (ll y : s) {
    if (x == -1 || dist[x][t] < dist[y][t]) {
      x = y;
    }
  }
  return x;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
  rep(i, 0, m) {
    g[a[i]].pb(b[i], t[i]); g[b[i]].pb(a[i], t[i]);
  }

  ll ans = 0;

  vi diam;
  rep(i, 0, n) if (!vis[i]) {
    dfs(i, -1, 0);
    ll x = get(0);
    dfs(x, -1, 1);
    ll y = get(1);
    dfs(y, -1, 2);

    ll res = (ll) 9e18;
    for (ll u : s) {
      res = min(res, max(dist[u][1], dist[u][2]));
      vis[u] = 1;
    }
    diam.pb(res);
    ans = max(ans, dist[y][1]);
  }

  sort(all(diam)); reverse(all(diam));

  if (diam.size() > 1) {
    ans = max(ans, diam[0] + diam[1] + l);
  }
  if (diam.size() > 2) {
    ans = max(ans, diam[1] + diam[2] + 2 * l);
  }

  return ans;
}

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