제출 #860037

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

race

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

using namespace std;


typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;

ll n, k;
vector<set<ii>> al;
vi size;
vi attached;
vi pathmin;
vi pathminbk;
ll pmbk = 0;
vii paths;
ll mink = INT_MAX;

void calcsize(ll u, ll p) {
  // cout << "calcsize" << " " << u << " " << p << endl;
  attached.emplace_back(u);
  size[u] = 1;
  for (auto &[v, w]:al[u]) if (v != p) {
    calcsize(v, u);
    size[u] += size[v];
  }
}

ll centoid(ll s) {
  attached.clear();
  calcsize(s, -1);
  ll ans = s;
  ll mimasub = size[s];
  for (auto &u:attached) {
    ll masub = attached.size() - size[u];
    for (auto &[v, _]:al[u]) if (size[v] < size[u]) {
      masub = max(masub, size[v]);
    }
    if (masub < mimasub) {
      ans = u;
      mimasub = masub;
    }
  }
  return ans;
}


void dfs1(ll u, ll p, ll nume, ll lene) {
  if (lene > k) return;
  paths.emplace_back(nume, lene);
  for (auto &[v,w]:al[u]) if (v != p) {
    dfs1(v, u, nume+1, lene+w);
  }
}

void calcpaths(ll s) {
  ll u = centoid(s);
  // cout << "centoid is " << u << endl;
  for (auto &[v, w]:al[u]) {
    paths.clear();
    dfs1(v, u, 1, w);
    for (auto &[nume, lene]:paths) {
      if (pathminbk[k-lene] == pmbk) {
        // if (pathmin[k-lene] + nume < mink) cout << "CHANGED k = " << k << " lene = " << lene << endl;
        mink = min(mink, pathmin[k-lene] + nume);
        
      }
    }
    for (auto &[nume, lene]:paths) {
      if (pathminbk[lene] != pmbk) {
        pathmin[lene] = nume;
        pathminbk[lene] = pmbk;
      }
      pathmin[lene] = min(pathmin[lene], nume);
    }
  }

  for (auto &[v, w]:al[u]) {
    al[v].erase(ii(u, w));
    pmbk++;
    pathmin[0] = 0;
    pathminbk[0] = pmbk;
    calcpaths(v);
  }

}


int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  k = K;
  pathmin.assign(k+10, INT_MAX);
  pathmin[0] = 0;
  pathminbk.assign(k+10, 0);
  size.assign(n, 0);
  al.resize(n);
  for (int i=0;i<n-1;i++) {
    ll u = H[i][0];
    ll v = H[i][1];
    al[u].emplace(v, L[i]);
    al[v].emplace(u, L[i]);
  }
  calcpaths(0);
  // for (int i=0;i<=k;i++) {
  //   cout << "k = " << i << ": " << pathmin[i] << endl;
  // }
  // cout << mink << endl;
  if (mink > n-1) return -1;

  return mink;
}

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

race.cpp: In function 'void calcsize(ll, ll)':
race.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |   for (auto &[v, w]:al[u]) if (v != p) {
      |              ^
race.cpp: In function 'll centoid(ll)':
race.cpp:39:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for (auto &[v, _]:al[u]) if (size[v] < size[u]) {
      |                ^
race.cpp: In function 'void dfs1(ll, ll, ll, ll)':
race.cpp:54:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |   for (auto &[v,w]:al[u]) if (v != p) {
      |              ^
race.cpp: In function 'void calcpaths(ll)':
race.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |   for (auto &[v, w]:al[u]) {
      |              ^
race.cpp:65:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |     for (auto &[nume, lene]:paths) {
      |                ^
race.cpp:72:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for (auto &[nume, lene]:paths) {
      |                ^
race.cpp:81:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |   for (auto &[v, w]:al[u]) {
      |              ^

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