oj.uz

Submission #816463

# Submission time Handle Problem Language Result Execution time Memory
816463 2023-08-09T05:11:56 Z Jarif_Rahman Highway Tolls (IOI18_highway) C++17
51 / 100
 214 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, m;
ll A, B;
vector<vector<pair<int, int>>> graph;
vector<int> depth, p, pe;

ll def;

void dfs(int nd, int dad, int dad_edge, int d){
    p[nd] = dad;
    depth[nd] = d;
    pe[nd] = dad_edge;
    for(auto [x, i]: graph[nd]) if(x != dad) dfs(x, nd, i, d+1);
}

int find_node(int root){
    dfs(root, -1, -1, 0);
    vector<int> o(n);
    for(int i = 0; i < n; i++) o[i] = i;
    sort(o.begin(), o.end(), [&](int a, int b){
        return depth[a] > depth[b];
    });

    ll def = ask(vector<int>(m, 0));

    int a = 0, b = n-1;
    while(a < b){
        int md = (a+b)/2;
        vector<int> w(m, 0);
        for(int i = 0; i <= md; i++) if(pe[o[i]] != -1) w[pe[o[i]]] = 1;
        ll x = ask(w);
        if(x > def) b = md;
        else a = md+1;
    }

    return o[a];
}

void find_pair(int _n, vector<int> U, vector<int> V, int _A, int _B){
    swap(n, _n);
    m = U.size();
    A = _A, B = _B;
    graph.resize(n);
    depth.resize(n);
    p.resize(n);
    pe.resize(n, -1);

    for(int i = 0; i < m; i++){
        graph[U[i]].pb({V[i], i});
        graph[V[i]].pb({U[i], i});
    }

    def = ask(vector<int>(m, 0));

    int s = find_node(0);
    int t = find_node(s);
    answer(s, t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 9 ms 1232 KB Output is correct
3 Correct 90 ms 8992 KB Output is correct
4 Correct 95 ms 8948 KB Output is correct
5 Correct 114 ms 9008 KB Output is correct
6 Correct 105 ms 8992 KB Output is correct
7 Correct 116 ms 8952 KB Output is correct
8 Correct 97 ms 8960 KB Output is correct
9 Correct 91 ms 8960 KB Output is correct
10 Correct 110 ms 8972 KB Output is correct
11 Correct 125 ms 9428 KB Output is correct
12 Correct 111 ms 10016 KB Output is correct
13 Correct 107 ms 9520 KB Output is correct
14 Correct 119 ms 9624 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1616 KB Output is correct
2 Correct 15 ms 2988 KB Output is correct
3 Correct 23 ms 4404 KB Output is correct
4 Correct 72 ms 12620 KB Output is correct
5 Correct 92 ms 12644 KB Output is correct
6 Correct 87 ms 12624 KB Output is correct
7 Correct 91 ms 12636 KB Output is correct
8 Correct 77 ms 12628 KB Output is correct
9 Correct 74 ms 12616 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 7 ms 1268 KB Output is correct
3 Correct 74 ms 7048 KB Output is correct
4 Correct 100 ms 9064 KB Output is correct
5 Correct 86 ms 9136 KB Output is correct
6 Correct 125 ms 8960 KB Output is correct
7 Correct 105 ms 8960 KB Output is correct
8 Correct 87 ms 9060 KB Output is correct
9 Correct 103 ms 8984 KB Output is correct
10 Correct 109 ms 8948 KB Output is correct
11 Correct 109 ms 9316 KB Output is correct
12 Correct 133 ms 9940 KB Output is correct
13 Correct 118 ms 9632 KB Output is correct
14 Correct 123 ms 9904 KB Output is correct
15 Correct 99 ms 9048 KB Output is correct
16 Correct 105 ms 8984 KB Output is correct
17 Correct 118 ms 9700 KB Output is correct
18 Correct 131 ms 9796 KB Output is correct
19 Correct 110 ms 8988 KB Output is correct
20 Correct 101 ms 10268 KB Output is correct
21 Correct 82 ms 9140 KB Output is correct
22 Correct 98 ms 9104 KB Output is correct
23 Correct 88 ms 9152 KB Output is correct
24 Correct 90 ms 9516 KB Output is correct
25 Correct 137 ms 12248 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 213 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 214 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -