Submission #1078610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078610		HorizonWest	Highway Tolls (IOI18_highway)	C++17	51 / 100	266 ms	262144 KiB

highway

#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
#include "highway.h"
using namespace std;

#define endl '\n'
#define db double
#define ll long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

long long ask(const std::vector<int> &w);
void answer(int s, int t);

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) 
{
    int M = U.size(), S, T;
    vector <vector<pair<int, int>>> v(N + 1, vector <pair<int, int>> ());

    for(int i = 0; i < M; i++)
    {
        int a = U[i], b = V[i];
        v[a].push_back({ b, i });
        v[b].push_back({ a, i });
    }

    vector <int> d(N+1), w(M);

    long long ivalue = ask(w); 

    vector <pair<int, int>> p(N+1, { 0, -1 }), t;

    auto Cdist = [&] (auto Cdist, int node, int parent) -> void
    {
        if(parent != -1) t.push_back({ d[node], p[node].sd });
        for(auto& u : v[node]) if(u.fs != parent)
        {   
            d[u.fs] = d[node] + 1;
            p[u.fs].fs = node; 
            p[u.fs].sd = u.sd;
            Cdist(Cdist, u.fs, node);
        }
    }; Cdist(Cdist, 0, -1);

    sort(all(t)); reverse(all(t));

    int a = -1, b = t.size()-1; 

    while (abs(a - b) != 1)
    {
        int c = (a + b) / 2; 

        for(int i = 0; i < M; i++){
            if(i <= c)
                w[t[i].sd] = 1; 
            else 
                w[t[i].sd] = 0;
        }

        if(ask(w) != ivalue)
            b = c;
        else 
            a = c;
    }

    b = t[b].sd;

    if(d[U[b]] > d[V[b]])
        S = U[b];
    else 
        S = V[b];

    for(int i = 0; i < M; i++){
        w[i] = 1;
    }

    int x = S; 
    vector <int> f(M);

    while (x != 0){
        f[p[x].sd] = 1;
        w[p[x].sd] = 0;
        x = p[x].fs;
    }

    if(ask(w) != ivalue)
    {
        a = -1; b = t.size()-1; 
        while (abs(a - b) != 1)
        {
            int c = (a + b) / 2; 

            for(int i = 0; i < M; i++){
                if(i <= c && f[t[i].sd] == 0)
                    w[t[i].sd] = 1; 
                else 
                    w[t[i].sd] = 0;
            }

            if(ask(w) != ivalue)
                b = c;
            else 
                a = c;
        }

        b = t[b].sd;

        if(d[U[b]] > d[V[b]])
            T = U[b];
        else 
            T = V[b];
    }
    else
    {
        vector <pair<int, int>> tx; 

        for(int i = 0; i < M; i++)
        {
            if(f[t[i].sd] == 1){
                tx.push_back(t[i]);
                //cerr << U[t[i].sd] << " " << V[t[i].sd]  << endl;
            }
        } t = tx; reverse(all(t));

        a = -1; b = t.size()-1; 
        while (abs(a - b) != 1)
        {
            int c = (a + b) / 2; 

            for(int i = 0; i < M; i++){
                w[i] = 0; 
            }

            for(int i = 0; i < M; i++){
                if(i <= c)
                    w[t[i].sd] = 1; 
            }

            if(ask(w) != ivalue)
                b = c;
            else 
                a = c;
        }

        b = t[b].sd;

        if(d[U[b]] < d[V[b]])
            T = U[b];
        else 
            T = V[b];
    }

    answer(S, T);
}

/*
N M A B S T
U[i] V[i]

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

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