Submission #465728

#	Time	Username	Problem	Language	Result	Execution time	Memory
465728		blue	Highway Tolls (IOI18_highway)	C++17	100 / 100	288 ms	11024 KiB

highway

#include "highway.h"
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

const int maxN = 90'000;

const int light = 0;
const int heavy = 1;

const int INF = 1e9;

int N;
vector<int> U;
vector<int> V;
long long A;
long long B;

int M;

int getV(int u, int e)
{
    return U[e] + V[e] - u;
}


vector<int> edge[maxN];

int middleEdge;

long long DA;


int X, Y;
const int Xtree = 0;
const int Ytree = 1;
const int notree = -1;

const int noedge = -1;


void find_pair(int n, vector<int> u, vector<int> v, int a, int b)
{
    N = n;
    U = u;
    V = v;
    A = a;
    B = b;

    M = U.size();

    for(int j = 0; j < M; j++)
    {
        edge[ U[j] ].push_back(j);
        edge[ V[j] ].push_back(j);
    }


    DA = ask(vector<int>(M, light));



    int lo = 0;
    int hi = M-1;
    while(lo != hi)
    {
        int mid = (lo+hi)/2;
        vector<int> w(M);
        for(int j = 0; j < M; j++)
        {
            if(j <= mid)
                w[j] = heavy;
            else
                w[j] = light;
        }

        if(ask(w) > DA) hi = mid;
        else lo = mid+1;
    }
    int middleEdge = lo;














    cerr << middleEdge << '\n';

    X = U[middleEdge]; //0
    Y = V[middleEdge]; //1

    vector<int> dist(N, INF);
    vector<int> tree(N, notree);
    vector<int> parentEdge(N, noedge);

    dist[X] = 0;
    tree[X] = Xtree;
    parentEdge[X] = noedge;

    dist[Y] = 0;
    tree[Y] = Ytree;
    parentEdge[Y] = noedge;


    queue<int> tbv;
    tbv.push(X);
    tbv.push(Y);

    vector<int> treelist[2];

    while(!tbv.empty())
    {
        int P = tbv.front();
        treelist[tree[P]].push_back(P);
        tbv.pop();
        for(int e: edge[P])
        {
            int Q = getV(P, e);
            if(dist[P] + 1 >= dist[Q]) continue;
            dist[Q] = dist[P] + 1;
            tree[Q] = tree[P];
            parentEdge[Q] = e;
            tbv.push(Q);
        }
    }

    // for(int i = 0; i < N; i++) cerr << dist[i] << ' ' << tree[i] << ' ' << parentEdge[i] << '\n';

    vector<int> ans;


    for(int Z = 0; Z < 2; Z++)
    {
        lo = 0;
        hi = int(treelist[Z].size()) - 1;
        // cerr << "Z = " << Z << '\n';
        // if(Z == 1)
        //     for(int t: treelist[Z]) cerr << t << ' ';
        //     cerr << '\n';
        // cerr << lo << ' ' << hi << '\n';
        while(lo != hi)
        {
            int mid = (lo+hi)/2;
            vector<int> w(M, heavy);
            w[middleEdge] = light;
            for(int i = 0; i < N; i++)
                if(parentEdge[i] != noedge)
                    w[parentEdge[i]] = light;
            // cerr << "mid = " << mid << '\n';
            // for(int i = 0; i <= mid; i++)
            // {
            //     if(parentEdge[ treelist[Z][i] ] != noedge)
            //         w[ parentEdge[ treelist[Z][i] ] ] = light;
            // }
            for(int i = mid+1; i <= hi; i++)
            {
                if(parentEdge[ treelist[Z][i] ] != noedge)
                    w[ parentEdge[ treelist[Z][i] ] ] = heavy;
            }

            // cerr << "query = ";
            // for(int h: w) cerr << h << ' ';
            // cerr << '\n';

            if(ask(w) > DA)
                lo = mid+1;
            else
                hi = mid;

            // cerr << lo << ' ' << hi << '\n';
        }
        ans.push_back(treelist[Z][lo]);
    }

    answer(ans[0], ans[1]);
}

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