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

highway

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

Subtask #1
5.0 / 5.0

#	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

Subtask #2
7.0 / 7.0

#	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

Subtask #3
6.0 / 6.0

#	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