Submission #917299

#	Time	Username	Problem	Language	Result	Execution time	Memory
917299		Taxiradio	Race (IOI11_race)	C++14	100 / 100	869 ms	35212 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

int n , k; 

vector<vector<pair<int , int>>> g;
vector<int> s;
vector<bool> removed;
vector<int> cnt;
int mdis =0;
int ans = INT_MAX;
int sz;
void get_subtree_size(int p){
    removed[p] = true;
    s[p] = 1;
    for(auto [x , y]:g[p]){
        if(!removed[x]){
            get_subtree_size(x);
            s[p] += s[x];
        }
    }
    removed[p] = false;
}

int get_centroid(int p){
    removed[p] = true;
    int centroid = p;
    for(auto [x , y]:g[p]){
        if(!removed[x] && s[x] > sz / 2){
            centroid = get_centroid(x);
            break;
        }
    }
    removed[p] = false;
    return centroid;
}

void dfs1(int p , int dis , int citys)
{
    if(k >= dis){
        ans = min(cnt[k-dis]+citys , ans);
    }else return;
    mdis = max(mdis , dis);
    removed[p] = true;
    for(auto [x , y]:g[p]){
        if(!removed[x]){
            dfs1(x , dis+y , citys+1);
        }
    }
    removed[p] = false;
}

void dfs2(int p , int dis , int citys)
{
    if(dis <= k)cnt[dis] = min(cnt[dis] , citys);else return;
    removed[p] = true;
    for(auto [x , y]:g[p]){
        if(!removed[x]){
            dfs2(x , dis+y , citys+1);
        }
    }
    removed[p] = false;
}

void solve(int p){
    mdis = 0;
    cnt[0] = 0;
    get_subtree_size(p);
    sz = s[p];
    int centroid = get_centroid(p);
    removed[centroid] = true;
    for(auto [x , y]: g[centroid]){
        if(!removed[x]){
            dfs1(x, y , 1);
            dfs2(x, y , 1);
        }
    }
    for(int i = 1; i <= mdis; i++){
        cnt[i] = INT_MAX-n;
    }
    for(auto [x , y]: g[centroid]){
        if(!removed[x]){
            solve(x);
        }
    }
}
int best_path(int N ,int K, int H[][2], int L[]){
	n = N;
	k = K;
	g.resize(n);
	s.resize(n);
	removed.resize(n);
    cnt.resize(k+1 , INT_MAX-n);
    for(int i = 0; i < n-1; i++){
        g[H[i][0]].push_back({H[i][1] , L[i]});
        g[H[i][1]].push_back({H[i][0] , L[i]});
    }
    solve(0);
	if(ans < n)return ans; else return -1;
}

Compilation message (stderr)

race.cpp: In function 'void get_subtree_size(int)':
race.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'int get_centroid(int)':
race.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'void dfs1(int, int, int)':
race.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'void dfs2(int, int, int)':
race.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'void solve(int)':
race.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for(auto [x , y]: g[centroid]){
      |              ^
race.cpp:82:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for(auto [x , y]: g[centroid]){
      |              ^

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