oj.uz

Submission #136944

# Submission time Handle Problem Language Result Execution time Memory
136944 2019-07-26T15:56:59 Z mlyean00 Race (IOI11_race) C++17
9 / 100
 119 ms 10292 KB 
#include "race.h"

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200'000;

int n, k;
int ans = INT_MAX;

struct state {
    int delta_k = 0;
    int delta_v = 0;
    map<int, int> min_n;

    state() {
        min_n[0] = 0;
    }

    void incr(int d) {
        delta_k += d;
        ++delta_v;
        auto it = min_n.find(k - delta_k);
        if (it != min_n.end()) ans = min(ans, it->second + delta_v);
        min_n.erase(min_n.upper_bound(k - delta_k), min_n.end());
    }

    void merge(state other) {
        if (min_n.size() < other.min_n.size()) {
            swap(delta_k, other.delta_k);
            swap(delta_v, other.delta_v);
            swap(min_n, other.min_n);
        }

        for (pair<int, int> const& p : other.min_n) {
            int key, val;
            tie(key, val) = p;
            key += other.delta_k;
            val += other.delta_v;
            auto it = min_n.find(key - delta_k);
            if (it == min_n.end()) {
                it = min_n.insert({key - delta_k, val - delta_v}).first;
            } else if (val < it->second + delta_v) {
                it->second = val - delta_v;
            }
            int rem = k - key;
            auto it2 = min_n.find(rem - delta_k);
            if (it2 != min_n.end()) {
                ans = min(ans, val + it2->second + delta_v);
            }
        }
    }
};

vector<int> g[MAX_N];
int parent[MAX_N];
int len[MAX_N];

void dfs1(int u) {
    for (int v : g[u]) {
        if (v == parent[u]) continue;
        parent[v] = u;
        dfs1(v);
    }
}

state dfs2(int u) {
    state st;
    for (int v : g[u]) {
        if (parent[v] == u) st.merge(dfs2(v));
    }
    st.incr(len[u]);
    return st;
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N, k = K;
    for (int i = 0; i < n - 1; ++i) {
        g[H[i][0]].push_back(H[i][1]);
        g[H[i][1]].push_back(H[i][0]);
    }

    dfs1(0);
    for (int i = 0; i < n - 1; ++i) {
        if (parent[H[i][1]] == H[i][0]) swap(H[i][0], H[i][1]);
        len[H[i][0]] = L[i];
    }
    dfs2(0);

    return ans == INT_MAX ? -1 : ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5008 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Correct 9 ms 5112 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5008 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Correct 9 ms 5112 KB Output is correct
19 Correct 7 ms 4984 KB Output is correct
20 Correct 6 ms 4984 KB Output is correct
21 Correct 7 ms 5112 KB Output is correct
22 Correct 7 ms 5112 KB Output is correct
23 Correct 7 ms 5288 KB Output is correct
24 Correct 7 ms 5112 KB Output is correct
25 Correct 8 ms 5240 KB Output is correct
26 Correct 7 ms 5112 KB Output is correct
27 Correct 7 ms 5112 KB Output is correct
28 Incorrect 8 ms 5112 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5008 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Correct 9 ms 5112 KB Output is correct
19 Incorrect 119 ms 10292 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5008 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5112 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Correct 9 ms 5112 KB Output is correct
19 Correct 7 ms 4984 KB Output is correct
20 Correct 6 ms 4984 KB Output is correct
21 Correct 7 ms 5112 KB Output is correct
22 Correct 7 ms 5112 KB Output is correct
23 Correct 7 ms 5288 KB Output is correct
24 Correct 7 ms 5112 KB Output is correct
25 Correct 8 ms 5240 KB Output is correct
26 Correct 7 ms 5112 KB Output is correct
27 Correct 7 ms 5112 KB Output is correct
28 Incorrect 8 ms 5112 KB Output isn't correct
29 Halted 0 ms 0 KB -