제출 #958295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958295		hariaakas646	경주 (Race) (IOI11_race)	C++14	100 / 100	370 ms	85984 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;

vector<vii> graph;
int n, k;
vector<mpii> val;
int out = 1e9;

pii dfs(int x, int pa) {
  val[x][0] = 0;
  int lt = 0;
  int dt = 0;
  // printf("%d: \n", x);
  for(auto e : graph[x]) {
    if(e.f != pa) {
      pii p1 = dfs(e.f, x);
      int l = p1.f + e.s;
      int d = p1.s + 1;
      // printf("%d\n", e.f);
      if(val[e.f].size() > val[x].size()) {
        for(auto p : val[x]) {

          auto it = val[e.f].find(k-(p.f+lt)-l);
          // printf("%d %d %d\n", p.f, lt, l);
          if(it != val[e.f].end()) {
            out = min(out, (*it).s + d + p.s + dt);
          }
        }
        swap(val[e.f], val[x]);
        for(auto pt : val[e.f]) {
          pii p = pt;
          p.f += lt - l;
          p.s += dt - d;

          if(val[x].find(p.f) == val[x].end()) val[x][p.f] = p.s;
          else
          val[x][p.f] = min(val[x][p.f], p.s); 
        }
        lt = l;
        dt = d;
      }
      else {
        for(auto p : val[e.f]) {
          auto it = val[x].find(k-(p.f+l)-lt);
          if(it != val[x].end()) {
            out = min(out, (*it).s + dt + p.s + d);
          }
        }
        for(auto pt : val[e.f]) {
          pii p = pt;
          p.f += l - lt;
          p.s += d - dt;
          if(val[x].find(p.f) == val[x].end()) val[x][p.f] = p.s;
          else
          val[x][p.f] = min(val[x][p.f], p.s); 
        }
      }
    }
  }
  return mp(lt, dt);
}

int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  k = K;
  graph = vector<vii>(n);

  frange(i, n-1) {
    graph[H[i][0]].pb(mp(H[i][1], L[i]));
    graph[H[i][1]].pb(mp(H[i][0], L[i]));
  }
  
  val = vector<mpii>(n);
  dfs(0, -1);
  if(out == 1e9) return -1;
  return out;
}

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