Submission #425264

#	Time	Username	Problem	Language	Result	Execution time	Memory
425264		arneves	Highway Tolls (IOI18_highway)	C++17	0 / 100	45 ms	5480 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)+1;
    w[0]=1;

    int l=0, r=N-2, m;
    if(ask(w)!=ultima){
        answer(0,tamanho-1);
        return;
    }
    {

        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<<'\n';
            atual=ask(w);

            if(atual/B==ultima/A){
                l=m+1;
            }else{
                r=m;
            }
        }
    }
    //cout<<m+1<<' '<<m+tamanho<<'\n';
    answer(m+1, m+tamanho);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:76:11: warning: 'm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |     answer(m+1, m+tamanho);
      |     ~~~~~~^~~~~~~~~~~~~~~~

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