Submission #1176639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176639		Luvidi	Highway Tolls (IOI18_highway)	C++20	51 / 100	89 ms	12048 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

const int maxn=90000;
vector<pii> ad[maxn+1];
int et[maxn+1],ep[maxn+1],tt;

void dfs(int v,int p){
    et[tt++]=v;
    for(auto[u,w]:ad[v])if(u!=p){
        ep[u]=w;
        dfs(u,v);
    }
}

void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B) {
    ll a=A,b=B;
    ll d=ask(vector<int>(n-1,0))/a;
    for(int i=0;i<n-1;i++){
        ad[u[i]].pb({v[i],i});
        ad[v[i]].pb({u[i],i});
    }
    dfs(0,0);
    int l=0,r=n-1;
    while(l<r){
        int m=(l+r)/2;
        vector<int> a(n-1);
        for(int i=1;i<=m;i++){
            a[ep[et[i]]]=1;
        }
        if(ask(a)==b*d)r=m;
        else l=m+1;
    }
    tt=0;
    int x=et[l];
    dfs(x,x);
    l=0,r=n-1;
    while(l<r){
        int m=(l+r)/2;
        vector<int> a(n-1);
        for(int i=1;i<=m;i++){
            a[ep[et[i]]]=1;
        }
        if(ask(a)==b*d)r=m;
        else l=m+1;
    }
    answer(x,et[l]);
}

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