oj.uz

Submission #155693

# Submission time Handle Problem Language Result Execution time Memory
155693 2019-09-29T23:18:20 Z rama_pang Highway Tolls (IOI18_highway) C++14
12 / 100
 468 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] || (dist[v] == dist[o.v] && v < 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;
            lint 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 3836 KB Output is correct
4 Correct 5 ms 3756 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3960 KB Output is correct
2 Correct 25 ms 4520 KB Output is correct
3 Correct 196 ms 10504 KB Output is correct
4 Correct 191 ms 10328 KB Output is correct
5 Correct 193 ms 10320 KB Output is correct
6 Correct 205 ms 10364 KB Output is correct
7 Correct 228 ms 10448 KB Output is correct
8 Correct 204 ms 10416 KB Output is correct
9 Correct 235 ms 10312 KB Output is correct
10 Correct 232 ms 10360 KB Output is correct
11 Correct 194 ms 11244 KB Output is correct
12 Correct 196 ms 11684 KB Output is correct
13 Correct 211 ms 11324 KB Output is correct
14 Correct 214 ms 10940 KB Output is correct

Subtask #3
0 / 6.0

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