Submission #1129722

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

race

# include <iostream>
# include <vector>
# include <map>
# include "race.h"
# include "grader.cpp"
using namespace std;

const int INF=1e9;
const int MAX=2e5+11;

int n,k;
vector<pair<int, long long>> adj[MAX];

int sz[MAX];
bool kill[MAX];
void dfs_sz(int curr, int par)
{
    sz[curr]=1;
    for(pair<int, long long> nxt: adj[curr])
    {
        if(nxt.first==par or kill[nxt.first]) continue;
        dfs_sz(nxt.first,curr);
        sz[curr]+=sz[nxt.first];
    }
}

int get_centroid(int curr, int par, int N)
{
    for(pair<int, long long> nxt: adj[curr])
    {
        if(nxt.first==par or kill[nxt.first]) continue;

        if(sz[nxt.first]*2>N) return get_centroid(nxt.first,curr,N);
    }

    return curr;
}

int ans=INF;
map<long long, int> mapi;

void add(long long x, int cnt)
{
    if(mapi.find(x)==mapi.end()) mapi[x]=cnt;
    else mapi[x]=min(mapi[x],cnt);
}

void dfs_ans(int curr, int par, long long dist, int cnt)
{
    if(mapi.find(k-dist)!=mapi.end()) ans=min(ans,cnt+mapi[k-dist]);

    for(pair<int, long long> nxt: adj[curr])
    {
        if(nxt.first==par or kill[nxt.first]) continue;
        dfs_ans(nxt.first,curr,dist+nxt.second,cnt+1);
    }
}

void dfs_fill(int curr, int par, long long dist, int cnt)
{
    add(dist,cnt);

    for(pair<int, long long> nxt: adj[curr])
    {
        if(nxt.first==par or kill[nxt.first]) continue;
        dfs_fill(nxt.first,curr,dist+nxt.second,cnt+1);
    }
}

void cd(int curr)
{
    dfs_sz(curr,-1);
    curr=get_centroid(curr,-1,sz[curr]);

    add(0,0);
    for(pair<int, long long> nxt: adj[curr])
    {
        if(kill[nxt.first]) continue;

        dfs_ans(nxt.first,curr,nxt.second,1);
        dfs_fill(nxt.first,curr,nxt.second,1);
    }
    mapi.clear();

    kill[curr]=1;
    for(pair<int, long long> nxt: adj[curr])
    {
        if(kill[nxt.first]) continue;
        cd(nxt.first);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n=N;k=K;
    for(int i=0;i<n-1;i++)
    {
        adj[H[i][0]].push_back({H[i][1],L[i]});
        adj[H[i][1]].push_back({H[i][0],L[i]});
    }

    cd(0);
    if(ans==INF) ans=-1;
    return ans;
}

/*
3 3
0 1 1
1 2 1
-1
*/

Compilation message (stderr)

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