Submission #497689

#	Time	Username	Problem	Language	Result	Execution time	Memory
497689		XII	Race (IOI11_race)	C++17	21 / 100	1267 ms	262148 KiB

race

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

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

const int INF = 1e9;
const int N = 2e5 + 1;
const int K = 1e6;
int n, k;
using pi = pair<int, int>;
vector<pi> adj[N];
multiset<pi> s[N];

int ans = INF;
void dfs(int u, int p = -1){
    s[u].insert({0, 0});
    for(auto [w, v]: adj[u]) if(v != p){
        dfs(v, u);
        for(auto p: s[v]) if(p.fi + w <= k){
            s[u].insert({p.fi + w, p.se + 1});
        } else break;
    }
    for(auto [w, v]: adj[u]) if(v != p){
        for(auto p: s[v]) if(p.fi + w <= k){
            s[u].erase(s[u].find({p.fi + w, p.se + 1}));
        } else break;
        for(auto p: s[v]) if(p.fi + w <= k){
            auto it = s[u].lower_bound({k - (p.fi + w), -1});
            if(it == s[u].end()) continue;
            if((*it).fi == k - (p.fi + w)){
                ans = min(ans, p.se + 1 + (*it).se);
            }
        } else break;
        for(auto p: s[v]) if(p.fi + w <= k){
            s[u].insert({p.fi + w, p.se + 1});
        } else break;
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N, k = K;
    FOR(i, 0, N - 1){
        adj[H[i][0]].eb(L[i], H[i][1]);
        adj[H[i][1]].eb(L[i], H[i][0]);
    }
    dfs(0);
    if(ans != INF) return ans;
    return -1;
}

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