Submission #1198464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198464		ozner77	Highway Tolls (IOI18_highway)	C++20	0 / 100	10 ms	3564 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<ll>> adj;
map<ll,map<ll,ll>> M;
vector<ll> depth,parent;
vector<vector<ll>> prof;
vector<int> w;
ll n;
void dfs(ll cur, ll prev) {
    prof[depth[cur]].push_back(cur);
    parent[cur]=prev;
    for (ll v:adj[cur]) {
        if (v!=prev){
            depth[v]=depth[cur]+1;
            dfs(v, cur);
        }
    }
}
/*int ask(int w[]){
    return 1;
}
void answer(ll x,ll y){
    cout<<x;
}*/
ll chance(ll cur){
    ll l,r,m;
    l=0;
    vector<ll> hijos;
    for (auto x:adj[cur]) {
        if (x!= parent[cur]) {
            hijos.push_back(x);
        }
    }
    r=hijos.size();
    while(l<r){
        m=(l+r)/2;
        for(ll i=0;i<=m;i++){
            w[M[cur][hijos[i]]]=0;
        }
        for(ll i=m+1;i<hijos.size();i++){
            w[M[cur][hijos[i]]]=1;
        }
        ll ans1=ask(w);
        for(ll i=0;i<=m;i++){
            w[M[cur][hijos[i]]]=1;
        }
        for(ll i=m+1;i<hijos.size();i++){
            w[M[cur][hijos[i]]]=0;
        }
        ll ans2=ask(w);
        if(ans1==ans2){
            return -1;
        }else if(ans1<ans2){
            l=m+1;
        }else{
            r=m;
        }
    }
    return hijos[l];
}
void find_pair(int N,vector<int> U,vector<int> V, int A, int B){
    adj.resize(N);
    prof.resize(N);
    depth.resize(N);
    w.resize(N);
    n=N;
    for(ll i=0;i<N;i++){
        w[i]=0;
    }
    for(int i=0;i<N-1;i++){
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
        M[U[i]][V[i]]=i;
        M[V[i]][U[i]]=i;
    }
    ll xd=ask(w);
    ll a=xd/A;
    depth[0]=0;
    dfs(0, -1);
    ll b=a-1;
    for(auto x:prof[b]){
        ll ans=chance(x);
        if(ans!=-1){
            answer(0,ans);
        }
    }
}

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