oj.uz

Submission #155663

# Submission time Handle Problem Language Result Execution time Memory
155663 2019-09-29T15:34:20 Z rama_pang Highway Tolls (IOI18_highway) C++14
5 / 100
 450 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[u] < dist[o.u];
    }
};
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 2
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 5 ms 3832 KB Output is correct
4 Correct 5 ms 3760 KB Output is correct
5 Correct 5 ms 3836 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 3832 KB Output is correct
2 Correct 24 ms 4472 KB Output is correct
3 Correct 202 ms 10428 KB Output is correct
4 Correct 202 ms 10500 KB Output is correct
5 Correct 189 ms 10324 KB Output is correct
6 Correct 210 ms 10324 KB Output is correct
7 Correct 204 ms 10328 KB Output is correct
8 Correct 192 ms 10448 KB Output is correct
9 Correct 191 ms 10432 KB Output is correct
10 Correct 176 ms 10308 KB Output is correct
11 Correct 223 ms 11240 KB Output is correct
12 Correct 212 ms 11688 KB Output is correct
13 Correct 206 ms 11340 KB Output is correct
14 Incorrect 214 ms 11032 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 5112 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 3832 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 450 ms 262144 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 365 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -