Submission #1244902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244902		joenpoenmanalt	Highway Tolls (IOI18_highway)	C++20	0 / 100	94 ms	8728 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);
    vi in_o(N), in_2(N);
    int idx = 0, idx2=0;
    auto dfs = [&](auto&& self, int p) -> void {
        if (vis[p]) return;
        vis[p] = 1;
        in_o[p] = idx++;
        for (auto [o, i] : adj[p]) {
            self(self, o);
        }
    };

    auto dfs2 = [&](auto&& self, int p) -> void {
        if (vis[p]) return;
        vis[p] = 1;
        in_2[p] = idx2++;
        for (int i_ = adj[p].size()-1; i_ >= 0; i_--) {
            auto [o, i] = adj[p][i_];
            self(self, o);
        }
    };
    dfs(dfs,0);
    vis = vi(N, 0);
    dfs2(dfs2,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 l = 0, h = idx;
        while (l < h) {
            int m = (l+h)/2;
            vi w(M, 0);
            for (int i = 0; i < N; i++) {
                if (in_o[i] >= m) for (auto [o, j] : adj[i]) w[j] = 1;
            }
            ll r = ask(w);
            if (r > og) l = m+1;
            else h = m;
        }
        for (int i = 0; i < N; i++) if (in_o[i] == l-1) s = i;
    }
    
    {
        int l = 0, h = idx;
        while (l < h) {
            int m = (l+h)/2;
            vi w(M, 0);
            for (int i = 0; i < N; i++) {
                if (in_2[i] >= m) for (auto [o, j] : adj[i]) w[j] = 1;
            }
            ll r = ask(w);
            if (r > og) l = m+1;
            else h = m;
        }
        for (int i = 0; i < N; i++) if (in_2[i] == l-1) t = i;
    }


    // 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 << s << ' ' << t << '\n';
    answer(s, t);
}


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

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

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