Submission #707856

#	Time	Username	Problem	Language	Result	Execution time	Memory
707856		Pherokung	Race (IOI11_race)	C++14	0 / 100	4 ms	8916 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];

int size(int u,int p){
    sz[u] = 1;
    for(auto [v,x] : adj[u]) if(!vis[v] && v != p) sz[u] += size(v,u);
    return sz[u];
}

int find_cen(int u,int p,int s){
    for(auto [v,x] : adj[u]) if(!vis[v] && v != p && sz[v] > s/2) return find_cen(v,u,s);
    return u;
}

void dfs(int u,int p,int len,int lv,int mode){
    if(len > k) return;
    if(mode == 0){
        ans = min(ans, lv + val[k - len]);
//        printf("!! %d %d : %d %d\n",u,len,lv,val[k-len]);
    }
    else if(mode == 1){
        val[len] = min(val[len],lv);
        //printf("!! %d %d\n",len,lv);
    }
    else if(mode == 2){
        if(len != 0) val[len] = 1e9;
    }

    for(auto [v,w] : adj[u]){
        if(!vis[v] && v != p){
            dfs(v,u,len+w,lv+1,mode);
        }
    }
}

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

    for(auto [v,w] : adj[c]){
        dfs(v,u,w,1,2);
    }

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

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

Compilation message (stderr)

race.cpp: In function 'int size(int, int)':
race.cpp:12:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   12 |     for(auto [v,x] : adj[u]) if(!vis[v] && v != p) sz[u] += size(v,u);
      |              ^
race.cpp: In function 'int find_cen(int, int, int)':
race.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [v,x] : adj[u]) if(!vis[v] && v != p && sz[v] > s/2) return find_cen(v,u,s);
      |              ^
race.cpp: In function 'void dfs(int, int, int, int, int)':
race.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for(auto [v,w] : adj[u]){
      |              ^
race.cpp: In function 'void process(int)':
race.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto [v,w] : adj[c]){
      |              ^
race.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     for(auto [v,w] : adj[c]){
      |              ^
race.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [v,w] : adj[c]){
      |              ^

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