Submission #1280029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280029		dex111222333444555	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define ii pair<int, int>
#define fi first
#define se second
#define sz(v) ((int)(v).size())
#define all(v) begin((v)), end(v)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define dbg(x) "[" #x " = " << x << "]"
using namespace std;
const int MAXN = 2e5 + 5, infINT = 1e9 + 23737, MAXV = 1e6 + 5;
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
int numNode, numReq, best[MAXV], sz[MAXN], res = MAXN + 1;
bool del[MAXN];
vector<ii> adj[MAXN];
vector<int> can;

void updateAns(int u, bool type, int sumDist, int step = 1, int par = 0){
    if (sumDist > numReq) return;
    can.push_back(sumDist);
    if (type){
        minimize(res, best[numReq - sumDist] + step);
    }else{
        minimize(best[sumDist], step);
    }
    for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
        int v = x.fi, w = x.se;
        updateAns(v, type, sumDist + w, step + 1, u);
    }
}

int getSize(int u, int par = 0){
    sz[u] = 1;
    for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
        int v = x.fi, w = x.se;
        sz[u] += getSize(v, u);
    }
    return sz[u];
}

int getCentroid(int sizeU, int u, int par = 0){
    for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
        int v = x.fi, w = x.se;
        if (sz[v] > (sizeU >> 1)) return getCentroid(sizeU, v, u);
    }
    return u;
}

void decomp(int u = 1){
    int centroid = getCentroid(getSize(u), u);
    del[centroid] = 1;

    can.clear();

    for(ii x: adj[centroid]) if (!del[x.fi]) {
        int v = x.fi, w = x.se;
        updateAns(v, true, w);
        updateAns(v, false, w);
    }

    for(int sumDist: can) best[sumDist] = infINT;

    for(ii x: adj[centroid]) if (!del[x.fi]){
        int v = x.fi, w = x.se;
        decomp(v);
    }
}

int best_path(int N, int K, int edge[][2], int len[])
{
    numNode = N; numReq = K;
    for(int i = 0; i < numNode - 1; i++){
        int u = edge[i][0] + 1, v = edge[i][1] + 1;
        adj[u].push_back({v, len[i]});
        adj[v].push_back({u, len[i]});
    }
    memset(best, 0x3f, sizeof best);
    best[0] = 0;
    decomp();
    return (res <= MAXN ? res: -1);
}

void solve(){
    int numNode = 11, numReq = 12;
    int edge[10][2] = {{0,1},{0,2},{2,3},{3,4},{4,5},{0,6},{6,7},{6,8},{8,9},{8,10}};
    int len[10] = {3,4,5,4,6,3,2,5,6,7};
    cout << best_path(numNode, numReq, edge, len) << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    cerr << TIME << ".s\n";
}

Compilation message (stderr)

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