Submission #816431

# Submission time Handle Problem Language Result Execution time Memory
816431 2023-08-09T05:05:34 Z Jarif_Rahman Highway Tolls (IOI18_highway) C++17
18 / 100
213 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;

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);
}

void find_pair(int _n, vector<int> U, vector<int> V, int _A, int _B){
    swap(n, _n);
    int 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});
    }

    dfs(0, -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));

    bool subtask3 = 1;
    for(int i = 0; i < n-1; i++) if(U[i] != i || V[i] != i+1) subtask3 = 0;

    if(subtask3){
        int s, t;
        {
            int a = 0, b = m-1;
            while(a < b){
                int md = (a+b)/2;
                vector<int> w(m, 0);
                for(int i = 0; i <= md; i++) w[i] = 1;
                ll x = ask(w);
                if(x > def) b = md;
                else a = md+1;
            }
            s = a;
        }
        {
            int a = 0, b = m-1;
            while(a < b){
                int md = (a+b+1)/2;
                vector<int> w(m, 0);
                for(int i = m-1; i >= md; i--) w[i] = 1;
                ll x = ask(w);
                if(x > def) a = md;
                else b = md-1;
            }
            t = a+1;
        }
        answer(s, t);
        return;
    }

    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;
    }

    answer(0, o[a]);
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 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 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 0 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 7 ms 1176 KB Output is correct
3 Correct 92 ms 8960 KB Output is correct
4 Correct 75 ms 8948 KB Output is correct
5 Correct 104 ms 8960 KB Output is correct
6 Correct 82 ms 8960 KB Output is correct
7 Correct 72 ms 8960 KB Output is correct
8 Correct 116 ms 8948 KB Output is correct
9 Correct 66 ms 8972 KB Output is correct
10 Correct 95 ms 8956 KB Output is correct
11 Correct 74 ms 9440 KB Output is correct
12 Correct 82 ms 9872 KB Output is correct
13 Correct 75 ms 9520 KB Output is correct
14 Correct 86 ms 9116 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 1616 KB Output is correct
2 Correct 13 ms 3020 KB Output is correct
3 Correct 16 ms 4400 KB Output is correct
4 Correct 62 ms 12628 KB Output is correct
5 Correct 72 ms 12636 KB Output is correct
6 Correct 112 ms 12624 KB Output is correct
7 Correct 91 ms 12636 KB Output is correct
8 Correct 79 ms 12724 KB Output is correct
9 Correct 62 ms 12632 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 213 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 193 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -