oj.uz

Submission #286379

# Submission time Handle Problem Language Result Execution time Memory
286379 2020-08-30T10:49:39 Z NONAME Highway Tolls (IOI18_highway) C++14
51 / 100
 224 ms 262148 KB 
#include "highway.h"

int m;
int res[2];
std::vector <int> w;
std::vector <std::pair <int, int> > g[(int)(1e5)], vec;

void dfs(int ve, int pr) {
    for (auto to : g[ve]) {
        if (to.first == pr)
            continue;

        vec.push_back(to);
        dfs(to.first, ve);
    }
}

int poisk(long long total, long long B) {
    int l = 0, r = (int)(vec.size()) - 1;
    while (l < r) {
        int md = (l + r) >> 1;

        for (int i = 1; i < (int)(vec.size()); ++i)
            w[vec[i].second] = (i <= md);

        if (ask(w) == total * B) r = md;
            else l = md + 1;
    }
    return l;
}

void find_pair (int n, std::vector <int> u, std::vector <int> v, int A, int B) {
    m = (int)(u.size());

    for (int i = 0; i < m; ++i) {
        g[u[i]].push_back(std::make_pair(v[i], i));
        g[v[i]].push_back(std::make_pair(u[i], i));
    }

    w.assign(m, 0);
    long long total = ask(w) / A;

    int s = 0;
    for (int _t = 0; _t < 2; ++_t) {
        vec.clear();
        vec.push_back(std::make_pair(0, -1));
        dfs(s, -1);

        int p = poisk(total, B);
        s = res[_t] = vec[p].first;
    }

    answer(res[0], res[1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 16 ms 3456 KB Output is correct
3 Correct 158 ms 8948 KB Output is correct
4 Correct 168 ms 8948 KB Output is correct
5 Correct 154 ms 8948 KB Output is correct
6 Correct 154 ms 8912 KB Output is correct
7 Correct 154 ms 8908 KB Output is correct
8 Correct 152 ms 8948 KB Output is correct
9 Correct 161 ms 8948 KB Output is correct
10 Correct 143 ms 9032 KB Output is correct
11 Correct 176 ms 10480 KB Output is correct
12 Correct 167 ms 11384 KB Output is correct
13 Correct 168 ms 10604 KB Output is correct
14 Correct 176 ms 10636 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 4352 KB Output is correct
2 Correct 27 ms 5876 KB Output is correct
3 Correct 41 ms 7412 KB Output is correct
4 Correct 150 ms 16668 KB Output is correct
5 Correct 125 ms 16580 KB Output is correct
6 Correct 129 ms 16628 KB Output is correct
7 Correct 121 ms 16636 KB Output is correct
8 Correct 130 ms 16592 KB Output is correct
9 Correct 126 ms 16596 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 15 ms 3456 KB Output is correct
3 Correct 113 ms 7796 KB Output is correct
4 Correct 158 ms 8948 KB Output is correct
5 Correct 153 ms 8948 KB Output is correct
6 Correct 155 ms 8948 KB Output is correct
7 Correct 154 ms 8948 KB Output is correct
8 Correct 152 ms 9108 KB Output is correct
9 Correct 195 ms 9076 KB Output is correct
10 Correct 202 ms 8948 KB Output is correct
11 Correct 167 ms 9644 KB Output is correct
12 Correct 218 ms 11504 KB Output is correct
13 Correct 173 ms 10864 KB Output is correct
14 Correct 166 ms 11232 KB Output is correct
15 Correct 152 ms 8948 KB Output is correct
16 Correct 153 ms 8948 KB Output is correct
17 Correct 206 ms 10992 KB Output is correct
18 Correct 163 ms 10976 KB Output is correct
19 Correct 150 ms 8948 KB Output is correct
20 Correct 211 ms 12140 KB Output is correct
21 Correct 127 ms 9452 KB Output is correct
22 Correct 128 ms 9580 KB Output is correct
23 Correct 179 ms 9324 KB Output is correct
24 Correct 136 ms 9960 KB Output is correct
25 Correct 152 ms 15756 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 224 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 221 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -