Submission #471172

#	Time	Username	Problem	Language	Result	Execution time	Memory
471172		jeroenodb	Race (IOI11_race)	C++14	100 / 100	424 ms	60404 KiB

race

#include "race.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 2e5+1, oo = 1e9;
static int ans,k;

struct paths {
    map<ll,int> m;
    ll delta=0;
    int extraedge=0;
    int get(ll l) {
        ll tmp = l-delta;
        auto iter = m.find(tmp);
        if(iter!=m.end()) return iter->second+extraedge;
        return oo;
    }
    void insert(ll l, int i) {
        i-=extraedge;
        ll tmp = l-delta;
        auto iter = m.find(tmp);
        if(iter!=m.end()) iter->second = min(i,iter->second);
        else m[tmp] = i;
    }
};
void merge(paths& a, paths& b) {
    if(a.m.size()<b.m.size()) swap(a,b);
    for(auto& p: b.m) {
        int real = p.first+b.delta;
        ans = min(ans,p.second+b.extraedge+a.get(k-real));
    }
    for(auto& p: b.m) {
        auto real = p.first+b.delta;
        a.insert(real,p.second+b.extraedge);
    }
}
vector<pi> adj[mxN];
void dfs(int at, int from, int ww, paths& parent) {
    paths p;
    p.insert(0,0);
    for(auto [to,w]: adj[at]) {
        if(to==from) continue;
        dfs(to,at,w,p);
    }
    p.delta+=ww,p.extraedge++;
    merge(parent,p);
}
int best_path(int N, int K, int H[][2], int L[]) {
    int n = N;
    k=K, ans = oo;
    for(int i=0;i<n;++i) adj[i].clear();
    for(int i=0;i<n-1;++i) {
        int a = H[i][0], b = H[i][1], w = L[i];
        adj[a].emplace_back(b,w);
        adj[b].emplace_back(a,w);
    }
    paths empty;
    dfs(0,-1,0,empty);
    return ans==oo?-1:ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, int, paths&)':
race.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto [to,w]: adj[at]) {
      |              ^

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