Submission #707887

#	Time	Username	Problem	Language	Result	Execution time	Memory
707887		Pherokung	Race (IOI11_race)	C++14	21 / 100	3071 ms	18088 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second

int n,k,sz[200005],lv[200005],vis[200005],ans=1e9,val[1000005];
vector<pair<int,int> > adj[200005];

void size(int u,int p)
{
    sz[u]=1;
    for(auto [node,w]:adj[u])
    {
        if(vis[node]==0&&node!=p)
        {
            size(node,u);
            sz[u]+=sz[node];
        }
    }
}
int find_cen(int u,int p,int want)
{
    for(auto [node,w]:adj[u])
    {
        if(node!=p&&vis[node]==0)
        {
            if(sz[node]>want)return find_cen(node,u,want);
        }
    }
    return u;
}

void dfs(int u,int p,int depth,int lv,int type)
{
    //printf("%lld %lld %lld %lld %lld\n",u,p,type,depth,lv);
    if(depth>k)return;
    if(type==1)
    {
        ans=min(ans,lv+val[k-depth]);
    }else if(type==0)
    {
        val[depth]=min(val[depth],lv);
    }else
    {
        val[depth]=1e9,val[k-depth]=1e9;
    }
    for(auto [node,w]: adj[u])
    {
        if(node!=p&&vis[node]==0) dfs(node,u,depth+w,lv+1,type);
    }
}

void process(int u){
    size(u,u);
    int c = find_cen(u,u,n/2);
    //printf("cen : %d\n",c);
    vis[c] = 1;

    for(auto [v,w] : adj[c]){
        if(!vis[v]){
            dfs(v,v,w,1,2);
        }
    }
    val[0] = 0;

    for(auto [v,w] : adj[c]){
        if(!vis[v]){
            dfs(v,v,w,1,1);
            dfs(v,v,w,1,0);
        }
    }

    for(auto [v,w] : adj[c]){
        if(!vis[v]){
            process(v);
        }
    }
}

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]+1].push_back({H[i][1]+1,L[i]});
        adj[H[i][1]+1].push_back({H[i][0]+1,L[i]});
    }
    for(int i=1;i<=n;i++)vis[i]=0;
    for(int i=1;i<=1000000;i++) val[i] = 1e9;
    process(1);
    return (ans == 1e9) ? -1 : ans;
}

Compilation message (stderr)

race.cpp: In function 'void size(int, int)':
race.cpp:13:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   13 |     for(auto [node,w]:adj[u])
      |              ^
race.cpp: In function 'int find_cen(int, int, int)':
race.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |     for(auto [node,w]:adj[u])
      |              ^
race.cpp: In function 'void dfs(int, int, int, int, int)':
race.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto [node,w]: adj[u])
      |              ^
race.cpp: In function 'void process(int)':
race.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for(auto [v,w] : adj[c]){
      |              ^
race.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for(auto [v,w] : adj[c]){
      |              ^
race.cpp:74:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for(auto [v,w] : adj[c]){
      |              ^

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