Submission #917290

#	Time	Username	Problem	Language	Result	Execution time	Memory
917290		Taxiradio	Race (IOI11_race)	C++17	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 best_path(int N ,int K, int* H[2], int* L){
	n = N;
	k = K;
	g.resize(n);
	s.resize(n);
	removed.resize(n);
    cnt.resize(1000 , INT_MAX-n);
    for(int i = 0; i < n-1; i++){
        g[H[i][0]].push_back({H[i][1] , L[i]});
        g[H[i][1]].push_back({H[i][0] , L[i]});
    }
    solve(0);
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void solve(int)':
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++){
      |                    ~~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccv4SeUm.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