제출 #1228882

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228882		JelalTkm	Race (IOI11_race)	C++20	100 / 100	694 ms	98052 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("fast-math")
#pragma GCC target("popcnt")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")

using namespace std;

#define ll long long int

const int N = 2e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;

int sz[N];
map<ll, pair<pair<int, int>, pair<int, int>>> mp;
vector<vector<pair<int, int>>> g(N, vector<pair<int, int>> ());
vector<vector<int>*> vec(N), vec1(N);
int dep[N];
int up[N][19];
ll sm[N];

void dfs(int u, int p) {
  up[u][0] = p;
  for (int i = 1; i <= 18; i++) {
    if (up[u][i - 1] != -1) {
      up[u][i] = up[up[u][i - 1]][i - 1];
    }
  }
  for (auto v: g[u])
    if (v.first != p) {
      dep[v.first] = dep[u] + 1;
      sm[v.first] = sm[u] + v.second;
      dfs(v.first, u);
      sz[u] += sz[v.first];
    }
}

int lca(int u, int v) {
  if (dep[u] > dep[v]) swap(u, v);
  int del = dep[v] - dep[u];
  for (int msk = 0; msk <= 18; msk++) {
    if (del & (1 << msk)) {
      v = up[v][msk];
    }
  }

  if (u == v) return u;

  for (int i = 18; i >= 0; i--)
    if (up[u][i] != up[v][i]) {
      u = up[u][i];
      v = up[v][i];
    }

  return up[u][0];
}

int ans = INF, kkk;

void dfs1(int u, int p, bool keep) {
  int sz_max = 0, bg = -1;
  for (auto v: g[u]) {
    if (v.first != p) {
      if (sz[v.first] > sz_max) {
        sz_max = sz[v.first];
        bg = v.first;
      }
    }
  }

  for (auto v: g[u]) {
    if (v.first != p && v.first != bg) {
      dfs1(v.first, u, 0);
    }
  }

  if (bg != -1) {
    dfs1(bg, u, 1);
    vec[u] = vec[bg];
  } else vec[u] = new vector<int> ();

  vec[u] -> push_back(u);

  if (mp[sm[u]].first.first >= dep[u] || mp[sm[u]].first.second == 0) {
    swap(mp[sm[u]].first, mp[sm[u]].second);
    mp[sm[u]].first = {dep[u], u};
  } else if (mp[sm[u]].second.first >= dep[u] || mp[sm[u]].second.second == 0) {
    mp[sm[u]].second = {dep[u], u};
  }


  for (auto v: g[u]) {
    if (v.first != p && v.first != bg) {
      for (auto i: *vec[v.first]) {
        vec[u] -> push_back(i);
        if (sm[i] == sm[up[i][0]]) continue;
        if (mp[sm[i]].first.first >= dep[i] || mp[sm[i]].first.second == 0) {
          swap(mp[sm[i]].first, mp[sm[i]].second);
          mp[sm[i]].first = {dep[i], i};
        } else if (mp[sm[i]].second.first >= dep[i] || mp[sm[i]].second.second == 0) {
          mp[sm[i]].second = {dep[i], i};
        }
        ll ss = sm[i] - sm[u];
        if (ss > kkk) continue;
        ll other = (kkk - ss) + sm[u];
        if (mp[other].first.second != 0 && lca(mp[other].first.second, i) == u) {
          ans = min(ans, (dep[i] - dep[u]) + (mp[other].first.first - dep[u]));
        }
        if (mp[other].second.second != 0 && lca(mp[other].second.second, i) == u) {
          ans = min(ans, (dep[i] - dep[u]) + (mp[other].second.first - dep[u]));
        }
      }
    }
  }

  if (mp[sm[u] + kkk].first.second != 0) {
    ans = min(ans, mp[sm[u] + kkk].first.first - dep[u]);
    // cout << u << " " << sm[u] + kkk << '\n';
  }

  if (keep == 0)
    mp = {};
}

int best_path(int n, int k, int h[][2], int l[]) {
  kkk = k;
  ans = INF;
  for (int i = 1; i <= n; i++) {
    sz[i] = 1;
    dep[i] = 1;
    sm[i] = 0ll;
    for (int j = 0; j < 19; j++)
      up[i][j] = -1;
  }
  vec = vec1;
  mp = {};
  for (int i = 1; i <= n; i++)
    g[i].clear();
  for (int i = 0; i < (n - 1); i++) {
    h[i][0]++, h[i][1]++;
    g[h[i][0]].push_back({h[i][1], l[i]});
    g[h[i][1]].push_back({h[i][0], l[i]});
  }

  dfs(1, -1);
  dfs1(1, -1, 1);
  if (ans == INF) ans = -1;
  return ans;
}

// int32_t main(int32_t argc, char *argv[]) {
//   ios::sync_with_stdio(false);
//   cin.tie(nullptr);

//   int T = 1;
//   // cin >> T;
//   while (T--) {
//     int n, k;
//     cin >> n >> k;
//     int h[n - 1][2], l[n - 1];
//     for (int i = 0; i < n - 1; i++)
//       cin >> h[i][0] >> h[i][1];
//     for (int i = 0; i < n - 1; i++)
//       cin >> l[i];

//     cout << best_path(n, k, h, l) << '\n';
//   }

//   return 0;
// }

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57