Submission #878970

#	Time	Username	Problem	Language	Result	Execution time	Memory
878970		MDSPro	Race (IOI11_race)	C++14	100 / 100	670 ms	52272 KiB

race

#include "race.h"
#include <vector>
#include <map>
 
using namespace std;
 
int K;
const int INF = 1e9;
vector<vector<pair<int, int>>> g;
vector<int> sz, vis;
 
int get_centroid(int root) {
    auto sub_size = [&](auto sub_size, int x, int p) -> void {
        sz[x] = 1; 
        for(auto [z, w]: g[x]) {
            if(z != p && vis[z] == 0) {
                sub_size(sub_size, z, x);
                sz[x] += sz[z];
            }
        }
    };
 
    sub_size(sub_size, root, -1);
    int n = sz[root];
    
    auto dfs = [&](auto dfs, int x, int p) -> int {
        for(auto [z, w]: g[x]) {
            if(z != p && vis[z] == 0) {
                if(2 * sz[z] > n) return dfs(dfs, z, x); 
            }
        }
 
        return x;
    };
 
    return dfs(dfs, root, -1);
}
 
int get(int c) {
    c = get_centroid(c);
 
    int ans = INF;
 
    map<int, int> mp;
    mp[0] = 0;
 
    vector<pair<int, int>> collect;
    auto dfs = [&](auto dfs, int x, int p, int s, int dep) -> void {
        if(s > K) return;
        if(mp.count(K - s)) ans = min(ans, mp[K - s] + dep);
        collect.emplace_back(s, dep);
 
        for(auto [z, w]: g[x]) {
            if(z != p && vis[z] == 0) {
                dfs(dfs, z, x, s + w, dep + 1);
            }
        }
    };
    
    vis[c] = 1;
    for(auto [z, w]: g[c]) {
        if(vis[z] == 0) {
            collect.clear();
            dfs(dfs, z, c, w, 1);
            
            for(auto [s, dep]: collect) {
                if(!mp.count(s) || mp[s] > dep) {
                    mp[s] = dep;
                }
            }
          
            ans = min(ans, get(z));
        }
    }
 
    return ans;
}
 
int best_path(int N, int K, int H[][2], int L[]) {
    ::K = K;
    g.resize(N);
    sz.resize(N);
    vis.resize(N);
 
    for(int i = 0; i < N - 1; ++i) {
        int x = H[i][0], y = H[i][1], w = L[i];
        g[x].emplace_back(y, w);
        g[y].emplace_back(x, w);
    }
 
    int ans = get(0);
    
    if(ans == INF) return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In lambda function:
race.cpp:15:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |         for(auto [z, w]: g[x]) {
      |                  ^
race.cpp: In lambda function:
race.cpp:27:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |         for(auto [z, w]: g[x]) {
      |                  ^
race.cpp: In lambda function:
race.cpp:53:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |         for(auto [z, w]: g[x]) {
      |                  ^
race.cpp: In function 'int get(int)':
race.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for(auto [z, w]: g[c]) {
      |              ^
race.cpp:66:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |             for(auto [s, dep]: collect) {
      |                      ^

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