Submission #1244932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244932		joenpoenmanalt	Highway Tolls (IOI18_highway)	C++20	0 / 100	73 ms	10168 KiB

highway

#include "highway.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

#define ALL(x) begin(x), end(x)

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    // cerr << "start\n";
    int M = U.size();
    vvii adj(N);
    for (int i = 0; i < M; i++) {
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    vi vis(N, 0);
    vis[0] = 1;
    vi edges;
    vi fv, lv;
    auto dfs = [&](auto&& self, int p) -> void {
        for (auto [o, i] : adj[p]) if (!vis[o]) {
            vis[o] = 1;
            edges.push_back(i);
            fv.push_back(p);
            lv.push_back(o);
            self(self, o);
            fv.push_back(o);
            lv.push_back(p);
            edges.push_back(i);
        }
    };

    dfs(dfs,0);
    
    ll og = ask(vi(M, 0));

    // for (int i = 0; i < N; i++) cerr << in_o[i] << ' ';  cerr << '\n';
    // for (int i = 0; i < N; i++) cerr << in_2[i] << ' ';  cerr << '\n';


    int s, t;
    int fst, lst;
    {
        int l = 0, h = edges.size();
        while (l < h) {
            int m = (l+h)/2;
            vi w(M, 1);
            for (int i = 0; i < m; i++) {
                w[edges[i]] = 0;
            }
            ll r = ask(w);
            if (r > og) l = m+1;
            else h = m;
        }
        lst = l-1;
    }
    
    {
        int l = 0, h = edges.size();
        while (l < h) {
            int m = (l+h+1)/2;
            vi w(M, 1);
            for (int i = edges.size()-1; i >= m; i--) {
                w[edges[i]] = 0;
            }
            ll r = ask(w);
            if (r > og) h = m-1;
            else l = m;
        }
        fst = l;
    }
    
    // if (edges[fst] == edges[fst+1]) fst++;
    // if (edges[lst] == edges[lst-1] && fst != lst) lst--;
    if (fst > lst) fst = lst;
    s = fv[fst];
    t = lv[lst];


    // for (int j = 0; j < 50; ++j)
    // {
    //     std::vector<int> w(M);
    //     for (int i = 0; i < M; ++i)
    //     {
    //         w[i] = 0;
    //     }
    //     long long toll = ask(w);
    // }
    // cerr << "done\n";
    // cerr << s << ' ' << t << '\n';
    answer(s, t);
}


/*
4 4 1 3 1 3
0 1
0 2
0 3
1 2

5 4 1 3 3 4
0 1
0 2
2 3
2 4

6 5 999999999 1000000000
0 1
0 2
4 2
0 3
3 5
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31