Submission #1114889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114889		DobromirAngelov	Race (IOI11_race)	C++14	100 / 100	572 ms	123920 KiB

race

#include "race.h"
#include<bits/stdc++.h>
 
#define fi first
#define se second
 
using namespace std;
 
const int MAXN=2e5+5;
const int MAXK=1e6+5;
const int INF=1e9+5;
 
int n,k;
vector<pair<int,int> > adj[MAXN];
int subtr[MAXN];
vector<int> ct_adj[MAXN];
vector<pair<long long,int> > ancs[MAXN];
bool rem[MAXN];
int minCnt[MAXK];
vector<pair<int,int> > upd;
vector<int> hist;
int ans=INF;
 
int get_subtr_sizes(int v,int par)
{
    subtr[v]=1;
    for(auto [u,w]: adj[v])
    {
        if(u==par || rem[u]) continue;
        subtr[v]+=get_subtr_sizes(u,v);
    }
    return subtr[v];
}
 
int get_centroid(int v,int par,int sz)
{
    for(auto [u,w]: adj[v])
    {
        if(u==par || rem[u]) continue;
        if(subtr[u]*2>sz) return get_centroid(u,v,sz);
    }
    return v;
}
 
void get_dists(int v,int par,long long dist,int cnt)
{
    ancs[v].push_back({dist, cnt});
    for(auto [u,w]: adj[v])
    {
        if(u==par || rem[u]) continue;
        get_dists(u, v, dist+w, cnt+1);
    }
}
 
int build_centroid_decomp(int v)
{
    int centroid=get_centroid(v, -1, get_subtr_sizes(v,-1));
 
    for(auto [u,w]: adj[centroid])
    {
        if(rem[u]) continue;
        get_dists(u,centroid,w,1);
    }
 
    rem[centroid]=1;
 
    for(auto [u,w]: adj[centroid])
    {
        if(rem[u]) continue;
        int cur=build_centroid_decomp(u);
        ct_adj[centroid].push_back(cur);
    }
    return centroid;
}
 
void dfs2(int v,int ptr)
{
    auto [dist, cnt] = ancs[v][ptr];
    if(-dist+k>=0) ans=min(ans, minCnt[k-dist]+cnt);
    if(dist>0 && dist<=k)
    {
        upd.push_back({dist, cnt});
        hist.push_back(dist);
    }
    for(auto u: ct_adj[v])
    {
        dfs2(u,ptr);
    }
}
 
void dfs(int v,int depth)
{
    for(auto u: ct_adj[v])
    {
        dfs2(u,depth);
        for(auto [dist,cnt]: upd)
        {
            minCnt[dist]=min(minCnt[dist],cnt);
        }
        upd.clear();
    }
    for(auto dist: hist)
    {
        minCnt[dist]=INF;
    }
  	hist.clear();
 
    for(auto u: ct_adj[v])
    {
        dfs(u,depth+1);
    }
}
 
void init_dfs()
{
    minCnt[0]=0;
    for(int i=1;i<=k;i++) minCnt[i]=INF;
    upd.reserve(n);
    hist.reserve(n);
}
 
int best_path(int N, int K, int H[][2], int L[])
{
    n=N; k=K;
    for(int i=0;i<n-1;i++)
    {
        int u=H[i][0]; u++;
        int v=H[i][1]; v++;
        int w=L[i];
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
 
    int root=build_centroid_decomp(1);
 
    init_dfs();
    dfs(root,0);
 
    if(ans>=INF) return -1;
    else return ans;
}

Compilation message (stderr)

race.cpp: In function 'int get_subtr_sizes(int, int)':
race.cpp:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto [u,w]: adj[v])
      |              ^
race.cpp: In function 'int get_centroid(int, int, int)':
race.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |     for(auto [u,w]: adj[v])
      |              ^
race.cpp: In function 'void get_dists(int, int, long long int, int)':
race.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto [u,w]: adj[v])
      |              ^
race.cpp: In function 'int build_centroid_decomp(int)':
race.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [u,w]: adj[centroid])
      |              ^
race.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for(auto [u,w]: adj[centroid])
      |              ^
race.cpp: In function 'void dfs2(int, int)':
race.cpp:78:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |     auto [dist, cnt] = ancs[v][ptr];
      |          ^
race.cpp: In function 'void dfs(int, int)':
race.cpp:96:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |         for(auto [dist,cnt]: upd)
      |                  ^

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