Submission #823246

#	Time	Username	Problem	Language	Result	Execution time	Memory
823246		Dremix10	Highway Tolls (IOI18_highway)	C++17	12 / 100	76 ms	15176 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;

    dfs(0,0,0,dep);
    assert(pos.size() > 0);
    int l = 0,r = pos.size() - 1;

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

        if(res != d){
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    answer(0,pos[r].S);
}

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