oj.uz

Submission #785837

# Submission time Handle Problem Language Result Execution time Memory
785837 2023-07-17T16:17:59 Z hcng Race (IOI11_race) C++14
0 / 100
 2 ms 5008 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5008 KB Output isn't correct
2 Halted 0 ms 0 KB -