Submission #785837

#	Time	Username	Problem	Language	Result	Execution time	Memory
785837		hcng	Race (IOI11_race)	C++14	0 / 100	2 ms	5008 KiB

race

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

struct Elem {
    long e;
    long v;
    
    Elem(long _e, long _v) {
        e = _e;
        v = _v;
    }
};

struct Cmp {
    bool operator() (const Elem &a, const Elem &b) {
        return a.v < b.v;
    }
} cmp;

vector<Elem> edge[200005];
vector<Elem> eseq;
bitset<200005> vis;
long last;

void dfs(long n, long cur) {
    vis[cur] = 1;
    eseq.emplace_back(cur, last);
    for (Elem e : edge[cur]) {
        long v = e.e, w = e.v;
        if (vis[v]) continue;
        last += w;
        dfs(n, v);
        last += w;
        eseq.emplace_back(cur, last);
    }
}

int best_path(int n, int k, int h[][2], int l[]) {
    
    last = 0;
    eseq.clear();
    vis.reset();
    
    for (long i = 0; i < n - 1; i++) {
        long u = h[i][0], v = h[i][1];
        long w = l[i];
        edge[u].emplace_back(v, w);
        edge[v].emplace_back(u, w);
    }
    dfs(n, 0);
    long m = eseq.size();
    long mindiff = 1e9;
    for (long i = 0; i < m; i++) {
        vector<Elem>::iterator it = lower_bound(
            eseq.begin(), eseq.end(), Elem{-1, eseq[i].v + k}, cmp
        );
        if (it->v != eseq[i].v + k) {
            continue;
        }
        long diff = (long)(it - eseq.begin()) - i;
        mindiff = min(mindiff, diff);
    }
    return mindiff;
}

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