Submission #377081

#	Time	Username	Problem	Language	Result	Execution time	Memory
377081		jeroenodb	Race (IOI11_race)	C++17	0 / 100	3 ms	5100 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) {
        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];
        int 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;
}

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