Submission #875589

#	Time	Username	Problem	Language	Result	Execution time	Memory
875589		abczz	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include <iostream>
#include <cstring>
#include <array>
#include <vector>
#include <queue>
#include <map>
#include "race.h"
#define ll long long

using namespace std;

bool iscent[200000];
bool del[200000];
vector <array<ll, 2> > adj[200000];
vector <array<ll, 2> > V;
queue <ll> Q;
map <ll, ll> dist;
ll n, k, a, b, c, cur, s, f = 1e18, rt, sz[200000];

ll dfs_sz(ll u, ll p) {
  ++s;
  sz[u] = 1;
  iscent[u] = true;
  for (auto [v, x] : adj[u]) {
    if (!del[v] && v != p) {
      sz[u] += dfs_sz(v, u);
    }
  }
  return sz[u];
}

void dfs_cent(ll u, ll w, ll p) {
  if (w > s/2) iscent[u] = false;
  for (auto [v, x] : adj[u]) {
    if (!del[v] && v != p) {
      if (sz[v] > s/2) iscent[u] = false;
      dfs_cent(v, w+sz[u]-sz[v], u);
    }
  }
  if (iscent[u]) rt = u;
}

void dfs(ll u, ll w, ll z, ll p) {
  if (k >= w) {
    if (dist.find(k-w) != dist.end()) {
      f = min(f, z+dist[k-w]);
    }
    for (auto [v, x] : adj[u]) {
      if (!del[v] && v != p) {
        dfs(v, w+x, z+1, u);
      }
    }
    V.push_back({w, z});
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> k;
  for (int i=0; i<n-1; ++i) {
    cin >> a >> b >> c;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }
  dfs_sz(0, -1);
  dfs_cent(0, 0, -1);
  Q.push(rt);
  for (int i=0; i<n; ++i) {
    cur = Q.front();
    Q.pop();
    del[cur] = true;
    dist.clear();
    dist[0] = 0;
    for (auto [v, x] : adj[cur]) {
      if (!del[v]) {
        dfs(v, x, 1, cur);
        while (!V.empty()) {
          if (dist.find(V[V.size()-1][0]) == dist.end()) {
            dist[V[V.size()-1][0]] = V[V.size()-1][1];
          }
          else dist[V[V.size()-1][0]] = min(dist[V[V.size()-1][0]], V[V.size()-1][1]);
          V.pop_back();
        }
      }
    }
    for (auto [v, x] : adj[cur]) {
      if (!del[v]) {
        s = 0;
        dfs_sz(v, cur);
        dfs_cent(v, 0, cur);
        Q.push(rt);
      }
    }
  }
  if (f == 1e18) cout << "-1\n";
  else cout << f << '\n';
}

Compilation message (stderr)

race.cpp: In function 'long long int dfs_sz(long long int, long long int)':
race.cpp:24:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |   for (auto [v, x] : adj[u]) {
      |             ^
race.cpp: In function 'void dfs_cent(long long int, long long int, long long int)':
race.cpp:34:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |   for (auto [v, x] : adj[u]) {
      |             ^
race.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
race.cpp:48:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for (auto [v, x] : adj[u]) {
      |               ^
race.cpp: In function 'int main()':
race.cpp:75:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     for (auto [v, x] : adj[cur]) {
      |               ^
race.cpp:87:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |     for (auto [v, x] : adj[cur]) {
      |               ^
/usr/bin/ld: /tmp/ccHQ8yr3.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cceubr25.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cceubr25.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status