Submission #823261

#	Time	Username	Problem	Language	Result	Execution time	Memory
823261		Dremix10	Highway Tolls (IOI18_highway)	C++17	6 / 100	101 ms	14348 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
const int N = 3e5+5;
const ll INF = 1e18+5;
const int MOD = 1e9+7;

vector<vector<pi> > a(N);
vector<pi> pos;
vector<pi> par(N);

void dfs(int s, int e, int cur, int f){
    if(cur == f){
        pos.push_back({par[s].S,s});
        return;
    }
    for(auto x : a[s]){
        if(x.F == e)continue;
        par[x.F] = {s,x.S};
        dfs(x.F,s,cur+1,f);
    }
}

void find_pair(int n, vector<int> u, vector<int> v, int A, int B) {
    int i;

    int m = u.size();

    for(i=0;i<m;i++){
        a[v[i]].push_back({u[i],i});
        a[u[i]].push_back({v[i],i});
    }

    vector<int> w(m,0);

    ll d = ask(w);
    int dep = d/A;

    int l = 0,r = n-2;

    while(l < r){
        int mid = (l+r)/2;
        for(i=0;i<=mid;i++){
            w[i] = 1;
        }
        ll res = ask(w);
        for(i=0;i<=mid;i++){
            w[i] = 0;
        }

        if(res != d){
            r = mid;
        }
        else{
            l = mid+1;
        }
    }

    int S = r;

    l = 1,r = n-1;

    while(l < r){
        int mid = (l+r+1)/2;
        for(i=n-1;i>=mid;i--){
            w[i-1] = 1;
        }
        ll res = ask(w);
        for(i=n-1;i>=mid;i--){
            w[i-1] = 0;
        }

        if(res != d){
            l = mid;
        }
        else{
            r = mid-1;
        }
    }

    int E = l;
    cerr<<S<<" "<<E<<endl;
    answer(S,E);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:43:9: warning: unused variable 'dep' [-Wunused-variable]
   43 |     int dep = d/A;
      |         ^~~

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