제출 #548611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548611		DavidDamian	경주 (Race) (IOI11_race)	C++11	100 / 100	486 ms	93388 KiB

race

#include "race.h"
#include <vector>
#include <map>
#include <climits>
#include <iostream>
#ifndef maxn
#define maxn 200005

using namespace std;
typedef long long ll;
struct edge {
  int to;
  ll w;
  edge() {

  }
  edge(int t, int w_) {
    to = t;
    w = w_;
  }
};

vector<edge> adjList[maxn];
int subtreeSize[maxn];
map<ll, int>* sack[maxn]; // Holds pairs (distance to root, min edges to root)
// cannot hold (distance to current node, min edges to current node) since these are relative and would have to be updated
int k; // Searched dist
int minimum; // Answer, minimum number of edges
void update(int u, ll dist, int depth) {
  if ((*sack[u]).find(dist) == (*sack[u]).end())
    (*sack[u])[dist] = INT_MAX;

  (*sack[u])[dist] = min((*sack[u])[dist], depth);
}

void printSack(int u) {
  cout << "Sack of " << u << endl;
  for (pair<ll, int> p : *sack[u]) {
    cout << p.first << " " << p.second << endl;
  }
  cout << endl;
}

void search(int u, int p, int greatestChild, int depth, ll dist) {

  for (edge e : adjList[u]) {
    int v = e.to;
    ll w = e.w;
    if (v == p || v == greatestChild) continue;
    for (pair<ll, int> curEndpoint : *sack[v]) {
      ll curDist = curEndpoint.first - dist;
      int curEdges = curEndpoint.second - depth;
      // Search for the complement
      int complement = k - curDist;
      int searchedComplement = complement + dist;
      if ((*sack[u]).find(searchedComplement) != (*sack[u]).end()) {
        // Found two-part path
        int edges = curEdges + (*sack[u])[searchedComplement] - depth;
        minimum = min(minimum, edges);
      }
    }

    // Copy information from this child in order to allow others to find routes to already computed child

    for (pair<ll, int> curEndpoint : *sack[v]) {
      update(u, curEndpoint.first, curEndpoint.second);
    }
  }

  int searchedDist = k + dist;
  if ((*sack[u]).find(searchedDist) != (*sack[u]).end()) { // Found one-part path
    int realEdgesCnt = (*sack[u])[searchedDist] - depth; // Edges relative to this node
    minimum = min(minimum, realEdgesCnt);
  }

}

void dfs(int u, int p, int depth, ll dist) {
  subtreeSize[u] = 1;
  int maxSubtreeSize = 0, greatestChild = -1;
  for (edge e : adjList[u]) {
    int v = e.to;
    ll w = e.w;
    if (v == p) continue;
    dfs(v, u, depth + 1, dist + w);
    subtreeSize[u] += subtreeSize[v];
    if (subtreeSize[v] > maxSubtreeSize) {
      maxSubtreeSize = subtreeSize[v];
      greatestChild = v;
    }
  }
  if (greatestChild == -1) {
    // Leaf node
    sack[u] = new map<ll, int>();
  }
  else {
    sack[u] = sack[greatestChild];
  }
  search(u, p, greatestChild, depth, dist);
  update(u, dist, depth);
}

int best_path(int N, int K, int H[][2], int L[])
{
  k = K;
  minimum = INT_MAX;
  for (int i = 0; i < N - 1; i++) {
    int a = H[i][0] + 1;
    int b = H[i][1] + 1;
    ll w = L[i];
    adjList[a].push_back(edge(b, w));
    adjList[b].push_back(edge(a, w));
  }
  dfs(1, 0, 0, 0);
  return (minimum == INT_MAX? -1 : minimum);
}

#endif

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'void search(int, int, int, int, ll)':
race.cpp:48:8: warning: unused variable 'w' [-Wunused-variable]
   48 |     ll w = e.w;
      |        ^

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