Submission #1136295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136295		Marko2604	Race (IOI11_race)	C++20	100 / 100	1923 ms	70984 KiB

race

#include<bits/stdc++.h>
#include "race.h"
#define ll long long
#define MAXN 200007
using namespace std;
vector<vector<pair<int,ll>>>T(MAXN);
bool used[MAXN];
int subtree[MAXN];
void subtreedfs(int node, int p=-1)
{
    subtree[node]=1;
    for(auto i:T[node]) if(!used[i.first] && i.first!=p)
    {
        subtreedfs(i.first,node);
        subtree[node]+=subtree[i.first];
    }
}
int getCentroid(int node, int subsz, int p=-1)
{
    for(auto i:T[node]) if(i.first!=p && !used[i.first] && subtree[i.first]*2>subsz) return getCentroid(i.first,subsz,node);
    return node;
}
ll depth[MAXN];
map<ll,int>m;
map<ll,bool>seen;
int k, ans=INT_MAX;
void dfs1(int node, int p, ll d, int d1)
{
    if(seen[k-d]) ans=min(ans,d1+m[k-d]);

    for(auto i:T[node]) if(i.first!=p && !used[i.first]) dfs1(i.first,node,d+i.second,d1+1);
}
void dfs2(int node, int p, ll d, int d1)
{
    depth[node]=d;
    if(seen[d]) m[d]=min(m[d],d1);
    else
    {
        m[d]=d1;
        seen[d]=true;
    }
    for(auto i:T[node]) if(i.first!=p && !used[i.first]) dfs2(i.first,node,d+i.second,d1+1);
}
void cenDec(int node)
{
    subtreedfs(node);
    int c=getCentroid(node,subtree[node]);
    used[c]=true;
    seen[0]=true;
    m[0]=0;
    for(auto i:T[c]) if(!used[i.first]) 
    {
        dfs1(i.first,c,i.second,1);
        dfs2(i.first,c,i.second,1);
    }
    m.clear();
    seen.clear();
    for(auto i:T[c]) if(!used[i.first]) cenDec(i.first);
}
int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    for(int i=0;i<N-1;i++)
    {
        T[H[i][0]].emplace_back(H[i][1],L[i]);
        T[H[i][1]].emplace_back(H[i][0],L[i]);
    }
    cenDec(1);
    if(ans==INT_MAX) return -1;
    return ans;
}

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