oj.uz

Submission #155665

# Submission time Handle Problem Language Result Execution time Memory
155665 2019-09-29T15:37:40 Z rama_pang Highway Tolls (IOI18_highway) C++14
5 / 100
 397 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MAXN = 150005;

lint N, M, A, B;
vector<int> G[MAXN];
lint dist[MAXN];
struct edge {
    int u, v, id;
    edge(int uu, int vv, int idd): u(uu), v(vv), id(idd) { }
    bool operator < (const edge &o) {
        return dist[v] < dist[o.v];
    }
};

vector<edge> E;

void dfs(int n, int p, int d) {
    dist[n] = d;
    for (auto &i : G[n]) if (i != p) {
        dfs(i, n, d + 1);
    }
}

void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) {
    N = _N, A = _A, B = _B, M = U.size();
    for (int i = 0; i < M; i++) {
        G[U[i]].emplace_back(V[i]);
        G[V[i]].emplace_back(U[i]);
        E.emplace_back(U[i], V[i], i);
    }
    dfs(0, -1, 0);
    for (int i = 0; i < M; i++) {
        if (dist[E[i].u] > dist[E[i].v]) swap(E[i].u, E[i].v);
    }
    sort(E.begin(), E.end());
    lint le = 0, ri = M - 1;
    lint ans = (dist[E.back().u] > dist[E.back().v])? E.back().u : E.back().v;
    vector<int> guess(M, 0);
    lint D = ask(guess) / A;
    while (le <= ri) {
        guess.assign(M, 0);
        lint mid = (le + ri) / 2;
        for (int i = 0; i <= mid; i++) guess[E[i].id] = 1;
        int check = ask(guess);
        // cout << le << " " << ri << " " << check << "\n";
        if (check == D * B) {
            ans = mid;
            ri = mid - 1;
        } else {
            // ans = mid;
            le = mid + 1;
        }
    }
    // cout << ans << "\n";
    ans = (dist[E[ans].u] == D)? E[ans].u : E[ans].v;
    answer(0, ans);
}

/*

4 4 1 3 1 3
0 1
0 2
0 3
1 2

4 3 1 3 0 1
0 1
0 2
0 3

4 3 1 3 0 1
0 1
0 3
1 2


*/

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3960 KB Output is correct
2 Correct 23 ms 4564 KB Output is correct
3 Correct 197 ms 10316 KB Output is correct
4 Correct 205 ms 10316 KB Output is correct
5 Correct 195 ms 10300 KB Output is correct
6 Correct 185 ms 10376 KB Output is correct
7 Correct 196 ms 10308 KB Output is correct
8 Correct 205 ms 10328 KB Output is correct
9 Correct 194 ms 10324 KB Output is correct
10 Correct 217 ms 10356 KB Output is correct
11 Correct 238 ms 11232 KB Output is correct
12 Correct 265 ms 11672 KB Output is correct
13 Correct 202 ms 11328 KB Output is correct
14 Incorrect 208 ms 11004 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 4984 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3960 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 397 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 359 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -