Submission #917293

#	Time	Username	Problem	Language	Result	Execution time	Memory
917293		Taxiradio	Race (IOI11_race)	C++14	31 / 100	272 ms	32032 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 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;
    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){
    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 < cnt.size(); 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(1000 , 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:16:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'int get_centroid(int)':
race.cpp:28:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'void dfs1(int, int, int)':
race.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'void dfs2(int, int, int)':
race.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for(auto [x , y]:g[p]){
      |              ^
race.cpp: In function 'void solve(int)':
race.cpp:70:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for(auto [x , y]: g[centroid]){
      |              ^
race.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 1; i < cnt.size(); i++){
      |                    ~~^~~~~~~~~~~~
race.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |     for(auto [x , y]: g[centroid]){
      |              ^

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