Submission #1287648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287648		islam_2010	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

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

const int sz = 2e5+5;
const int inf = 1e9 + 7;
vector<pair<int, int>> g[sz];
vector<int> sub(sz);
vector<bool> isremoved(sz);
int mn;
int subtree_size(int node, int p = -1){
    sub[node] = 1;
    for(auto i: g[node]){
        if(isremoved[i.first] || i.first == p) continue;
        sub[node] += subtree_size(i.first, node);
    }return sub[node];
}

int get_centroid(int node, int stsz, int p = -1){

    for(auto i: g[node]){
        if(isremoved[i.first] || i.first == p) continue;
        if(sub[i.first] * 2 > stsz){
            return get_centroid(i.first, stsz, node);
        }
    }return node;
}

void search(int node, int p, int d, int dist, int k, vector<pair<int,int>>& vals) {
    if (d > k) return;  
    vals.push_back({d, dist});
    for (auto i : g[node]) {
        if (isremoved[i.first] || i.first == p) continue;
        search(i.first, node, d + i.second, dist + 1, k, vals);
    }
}


void build(int node, int k){
    int stsz = subtree_size(node);
    int cent = get_centroid(node, stsz);
    isremoved[cent] = true;
    map<int,int> mp;
    mp[0] = 0;
    for(auto i: g[cent]){
        if(isremoved[i.first]) continue;

        vector<pair<int,int>> vals;
        search(i.first, cent, i.second, 1 , k, vals);

        for(auto [d, dist]: vals){
            
            if(mp.count(k-d)){
                mn = min(mn, mp[k-d]+dist);
            }
        }
        for(auto [d, dist]: vals){
            if(!mp.count(d)){
                mp[d] = dist;
            }else {
                mp[d] = min(mp[d], dist);
            }
        }

    }
    
    
    for(auto i: g[cent]){
        if(!isremoved[i.first]){
            build(i.first, k);
        }
    }


}

int best_path(int N, int K, int H[][2], int L[]){
    for (int i = 0; i <= N; i++) {
        g[i].clear();
        isremoved[i] = false;
    }

    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]});
    }mn = inf;
    build(0, K);
    return (mn == inf ? -1 : mn);
}
int main() {
    int N = 4, K = 11;
    int h[3][2] = {{0, 1}, {1, 2}, {2, 3}};
    int L[3] = {5, 6, 7};

    cout << best_path(N, K, h, L);
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccp2QpzV.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccmF7DIM.o:race.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status