Submission #917286

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

race

#include <bits/stdc++.h>
using namespace std;

int n , k; 

vector<vector<pair<int , int>>> g;
vector<int> s;
vector<bool> removed;
vector<int> cnt;
int ans = INT_MAX;
int sz;
void get_subtree_size(int p){
    removed[p] = true;
    s[p] = 1;
    for(auto [x , y]:g[p]){
        if(!removed[x]){
            get_subtree_size(x);
            s[p] += s[x];
        }
    }
    removed[p] = false;
}

int get_centroid(int p){
    removed[p] = true;
    int centroid = p;
    for(auto [x , y]:g[p]){
        if(!removed[x] && s[x] > sz / 2){
            centroid = get_centroid(x);
            break;
        }
    }
    removed[p] = false;
    return centroid;
}

void dfs1(int p , int dis , int citys)
{
    if(k >= dis){
        ans = min(cnt[k-dis]+citys , ans);
    }else return;
    removed[p] = true;
    for(auto [x , y]:g[p]){
        if(!removed[x]){
            dfs1(x , dis+y , citys+1);
        }
    }
    removed[p] = false;
}

void dfs2(int p , int dis , int citys)
{
    if(dis <= k)cnt[dis] = min(cnt[dis] , citys);else return;
    removed[p] = true;
    for(auto [x , y]:g[p]){
        if(!removed[x]){
            dfs2(x , dis+y , citys+1);
        }
    }
    removed[p] = false;
}

void solve(int p){
    cnt[0] = 0;
    get_subtree_size(p);
    sz = s[p];
    int centroid = get_centroid(p);
    removed[centroid] = true;
    for(auto [x , y]: g[centroid]){
        if(!removed[x]){
            dfs1(x, y , 1);
            dfs2(x, y , 1);
        }
    }
    for(int i = 1; i < cnt.size(); i++){
        cnt[i] = INT_MAX-n;
    }
    for(auto [x , y]: g[centroid]){
        if(!removed[x]){
            solve(x);
        }
    }
}

int main() {

    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> k;
    g.resize(n);
	s.resize(n);
	removed.resize(n);
    cnt.resize(1000 , INT_MAX-n);
    for(int i = 0; i < n-1; i++){
        int a , b ,c; cin >> a >> b >> c;
        g[a].push_back({b , c});
        g[b].push_back({a , c});
    }
    solve(0);
	cout << ans;
}

Compilation message (stderr)

race.cpp: In function 'void get_subtree_size(int)':
race.cpp:15:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'int get_centroid(int)':
race.cpp:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'void dfs1(int, int, int)':
race.cpp:43:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'void dfs2(int, int, int)':
race.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'void solve(int)':
race.cpp:69:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for(auto [x , y]: g[centroid]){
      |              ^
race.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i = 1; i < cnt.size(); i++){
      |                    ~~^~~~~~~~~~~~
race.cpp:78:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |     for(auto [x , y]: g[centroid]){
      |              ^
/usr/bin/ld: /tmp/cc4Ua7mk.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccXjLacj.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccXjLacj.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