Submission #263056

#	Time	Username	Problem	Language	Result	Execution time	Memory
263056		Nightlight	Race (IOI11_race)	C++14	43 / 100	410 ms	78456 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

int N, K;
map<long long, int> mp[200005];
vector<pii> adj[200005];
long long dist[200005];
int cnt[200005];
int ans = 1000000;

void DFS(int u, int p = N) {
  int v, w;
  mp[u][dist[u]] = cnt[u];
  for(pii now : adj[u]) {
    v = now.second, w = now.first;
    if(v == p) continue;
    dist[v] = dist[u] + w;
    cnt[v] = cnt[u] + 1;
    DFS(v, u);
    if(mp[v].size() > mp[u].size()) swap(mp[v], mp[u]);
  }
  long long jarak;
//  cout << u << " -> " << dist[u] << " " << cnt[u] << "\n";
  for(pii now : adj[u]) {
    v = now.second;
    if(v == p) continue;
//    cout << v << ":\n";
    for(pii it : mp[v]) {
      jarak = dist[u] * 2 + K - it.first;
      if(mp[u].count(jarak)) {
        ans = min(ans, mp[u][jarak] + it.second - cnt[u] * 2);
      }
      if(mp[u].count(it.first)) mp[u][it.first] = min(mp[u][it.first], it.second);
      else mp[u][it.first] = it.second;
    }
    mp[v].clear();
  }
}

int best_path(int n, int k, int H[][2], int L[]) {
  N = n, K = k;
  for(int i = 0; i < N - 1; i++) {
    adj[H[i][0]].emplace_back(L[i], H[i][1]);
    adj[H[i][1]].emplace_back(L[i], H[i][0]);
  }
  DFS(0);
  if(ans == 1000000) return -1;
  return ans;
}

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