Submission #1281051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281051		david_g611	Race (IOI11_race)	C++20	21 / 100	3097 ms	46096 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

const int NMAX=2e5;
vector<pair<int, int>> g[NMAX+1];
int sz[NMAX+1];
bool elim[NMAX+1];

void get_subtree_size(int nod, int par=-1)
{
    sz[nod]=1;
    for(auto &[copil, cost]:g[nod])
    {
        if(copil!=par && !elim[copil])
        {
            get_subtree_size(copil, nod);
            sz[nod]+=sz[copil];
        }
    }
}

int find_centroid(int nod, int tree_size, int par=-1)
{
    for(auto &[copil, cost]:g[nod])
    {
        if(copil!=par && !elim[copil])
        {
            if(sz[copil] * 2 > tree_size)
                return find_centroid(copil, tree_size, nod);
        }
    }
    return nod;
}

struct myHash
{
    const int operator ()(const int &x) const{
        return x^(x>>1);
    }
};
unordered_map<int, int, myHash> minpath;
int ans=1e9;
int target;
///minpath[i]=nrmin de drumuri cu suma costurilor = i

void dfs(int nod, int par, int dist, int h, bool calc)
{
    if(calc==1 && minpath[target-dist]!=0)
    {
        ans=min(ans, h+minpath[target-dist]);
    }
    if(calc==0)
    {
        if(minpath[dist]==0)minpath[dist]=h;
        else minpath[dist]=min(minpath[dist], h);
    }
    for(auto &[copil, cost]:g[nod])
        if(copil!=par && !elim[copil])
            dfs(copil, nod, cost+dist, h+1, calc);
}

void decomp(int nod)
{
    get_subtree_size(nod);
    int centroid=find_centroid(nod, sz[nod]);

    ///fac ceva
    minpath[0]=1;
    for(auto &[copil, cost]:g[centroid])
        if(!elim[copil])
        {
            dfs(copil, centroid, cost, 2, 1);
            dfs(copil, centroid, cost, 2, 0);
        }

    minpath.clear();
    elim[centroid]=1;
    for(auto &[copil, cost]:g[centroid])
        if(!elim[copil])
            decomp(copil);
}

int best_path(int N, int K, int H[][2], int L[])
{
    target=K;
    for(int i=0; i<N-1; i++)
    {
        int x=H[i][0], y=H[i][1], z=L[i];
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    decomp(0);
    if(ans==1e9)ans=1;
    return ans-2;
}

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