Submission #1129723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129723		denislav	Race (IOI11_race)	C++20	100 / 100	1137 ms	45828 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
*/

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57