Submission #899937

#	Time	Username	Problem	Language	Result	Execution time	Memory
899937		Macker	Race (IOI11_race)	C++14	31 / 100	2978 ms	262144 KiB

race

#include "race.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")

vector<vector<pair<int, int>>> adj;
int k;

pair<multiset<pair<int, int>>, int> dfs(int a, int p){
    multiset<pair<int, int>> cur;
    cur.insert({0, 0});
    int res = INT_MAX;
    vector<vector<pair<int, int>>> ch;
    vector<int> mn(k + 1, INT_MAX);
    for (auto [b, c] : adj[a]) {
        if(b == p) continue;
        ch.push_back({});
        auto [s, x] = dfs(b, a);
        res = min(res, x);
        for (auto &i : s) {
            if(i.first + c > k) continue;
            ch.back().push_back({i.first + c, i.second + 1});
            mn[i.first + c] = min(mn[i.first + c], i.second + 1);
        }
    }
    
    


    for (auto &&i : ch) for (auto &&j : i){
        if(j.second == mn[j.first])
            cur.insert(j);
    } 

    for (auto &&i : ch) {
        for (auto &&j : i){
            if(j.second == mn[j.first])
                cur.erase(cur.find(j)); 
        } 
        for (auto &&j : i) {
            if(j.second != mn[j.first]) continue;
            if(cur.lower_bound({k - j.first, 0}) == cur.end()) continue;
            pair<int, int> x = *cur.lower_bound({k - j.first, 0});
            if(x.first == k - j.first){
                res = min(res, x.second + j.second);
            }
        }
        for (auto &&j : i){
            if(j.second == mn[j.first])
                cur.insert(j);
        } 
    }
    return {cur, res};
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    adj.assign(N, {});
    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]});
    }
    int ret = dfs(0, 0).second;
    if(ret == INT_MAX) return -1;
    return ret;
}

Compilation message (stderr)

race.cpp: In function 'std::pair<std::multiset<std::pair<int, int> >, int> dfs(int, int)':
race.cpp:21:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |     for (auto [b, c] : adj[a]) {
      |               ^
race.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |         auto [s, x] = dfs(b, a);
      |              ^

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