제출 #742236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
742236		beaboss	경주 (Race) (IOI11_race)	C++14	9 / 100	45 ms	25664 KiB

race

#include <bits/stdc++.h>

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

const ll MN = 3e5 + 10;

vpii adj[MN];
ll d[MN]; // from root in highways
ll d2[MN]; // from root in distance
ll k;
void dfs(ll cur = 0, ll dist = 0, ll dist2 = 0, ll p = -1) {
  // cout << cur << endl;
  d[cur]=dist;
  d2[cur]=dist2;

  for (auto val: adj[cur]) {
    if (val.f != p) {
      dfs(val.f, dist + 1, dist2 + val.s, cur);
    }
  }
}

map<ll, ll> small[MN];

ll ans = 1e9;

void solve(ll cur, ll p=-1) {
  
  for (auto val: adj[cur]) {
    if (val.f != p) {
      solve(val.f, cur);
      // cout << ' ' << val.f << ' ' << cur << d2[cur] << endl;
      if (small[val.f].find(k + d2[cur]) != small[val.f].end()) {
      	// cout << "  " << small[val.f][k + d2[cur]] << d[cur] << endl;
      	ans = min(ans, small[val.f][k + d2[cur]] - d[cur]);
      	// cout << ans << endl;
      }
      if (small[val.f].size() > small[cur].size()) swap(small[val.f], small[cur]);

      // merge

      for (pii nx: small[val.f]) {
        if (small[cur].find(k + 2*d2[cur] - nx.f) != small[cur].end()) {
          
          ans = min(ans, small[cur][k + 2*d2[cur] - nx.f] + nx.s - d[cur]);
        }
      }

      for (pii nx: small[val.f]) {
        if (small[cur].find(nx.f) == small[cur].end()) small[cur][nx.f]=nx.s;
        else small[cur][nx.f]=min(small[cur][nx.f], nx.s);
      }
    }

  }

  if (small[cur].find(d2[cur]) == small[cur].end()) small[cur][d2[cur]]=d[cur];
  else small[cur][d2[cur]]=min(small[cur][d2[cur]], d[cur]);
  // cout << cur << endl;
  // for (auto val: small[cur]) {
  // 	cout << val.f << val.s << endl;
  // }
  
}



int best_path(int N, int K, int H[][2], int L[])
{

  k = K;
  FOR(i, 0, N-1) {
    adj[H[i][0]].pb({H[i][1], L[i]});
  }

  dfs();
  solve(0);
  if (ans == 1e9) ans = -1;
  return ans;
}

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