Submission #425267

#	Time	Username	Problem	Language	Result	Execution time	Memory
425267		arneves	Highway Tolls (IOI18_highway)	C++17	6 / 100	134 ms	6768 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> adj[200000];
/*
5 4 16 20 1 4
0 1
1 2
2 3
3 4
****************
5 4 16 20 1 3
0 1
1 2
2 3
3 4
****************
5 4 16 20 0 2
0 1
1 2
2 3
3 4
****************
5 4 16 20 3 4
0 1
1 2
2 3
3 4
*/
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {

    int M=U.size();

    ll tamanho;

    vector<int> w(M,0);

    ll ultima=ask(w), atual;

    tamanho=(ultima/A);
    w[0]=1;

    int l=0, r=N-2, m;

    while(l<r){
        m=(l+r)/2;

        for(int i=0; i<M; i++){
            if(i<=m){
                w[i]=0;
            }else{
                w[i]=1;
            }
            //cout<<w[i]<<' ';
        }
        //cout<<"->"<<m<<'\n';
        atual=ask(w);

        if(atual==ultima){
            r=m-1;
        }else if(atual/B==ultima/A){
            l=m+1;
        }else{
            r=m;
        }
    }

    //cout<<l<<' '<<l+tamanho<<'\n';
    answer(l, l+tamanho);
}

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