Submission #1014185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014185		Dzadzo	Highway Tolls (IOI18_highway)	C++17	12 / 100	90 ms	34632 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF INT_MAX
#define MOD 1000000007
#define MAXN 100000
using namespace std;
 
/*
ll ask(vi arr) {
    for (int x:arr)cout<<x<<" ";
    cout<<'\n';
    ll res;
    cin>>res;
    return res;
}
void answer(int x,int y) {
    cout<<x<<" "<<y<<"\n";
}
*/
 
vi edges;
vvp adj(MAXN+1);
vvp depth(MAXN+1);
 
 
void dfs(int v,int p,int d) {
    for (auto &[to,id]:adj[v]) {
        if (to==p)continue;
        depth[d].pb({to,id});
        edges.pb(id);
        dfs(to,v,d+1);
    }
}
void find_pair(int n,vi U,vi V,int A,int B) {
    for (int i=0;i<n-1;i++) {
        adj[U[i]].pb({V[i],i});
        adj[V[i]].pb({U[i],i});
    }
    vi w(n-1);
    ll dist=ask(w);
    int res=-1;
    for (int bit=15;bit>=0;bit--) {
        if (res+(1<<bit)>=n-1)continue;
        for (int i=0;i<=res+(1<<bit);i++)w[i]=1;
        ll cur=ask(w);
        for (int i=0;i<=res+(1<<bit);i++)w[i]=0;
        if (cur==dist)res+=(1<<bit);
 
    }
    res++;
    // cout<<V[res]<<" "<<U[res]<<'\n';
 
    depth[0].pb({V[res],res});
 
    dfs(V[res],U[res],1);
    for (int x:edges)w[x]=1;
    ll distx=( ask (w) - dist ) / ( B - A );
    for (int x:edges)w[x]=0;
    ll disty= dist/A - distx - 1;
 
    // cout<<distx<<" "<<disty<<"\n";
    int idx=-1;
    for (int bit=15;bit>=0;bit--) {
        if ( idx+(1<<bit) >= depth[distx].size() )continue;
        for (int i=0;i<=idx+(1<<bit);i++)w[depth[distx][i].S]=1;
        ll cur=ask(w);
        for (int i=0;i<=idx+(1<<bit);i++)w[depth[distx][i].S]=0;
        if (cur == dist )idx+=(1<<bit);
    }
    idx=depth[distx][idx+1].F;
 
    depth.assign(MAXN+1,{});
    depth[0].pb({U[res],res});
    dfs(U[res],V[res],1);
 
    int idy=-1;
    for (int bit=15;bit>=0;bit--) {
        if ( idy+(1<<bit) >= depth[disty].size() )continue;
        for (int i=0;i<=idy+(1<<bit);i++)w[depth[disty][i].S]=1;
        ll cur=ask(w);
        for (int i=0;i<=idy+(1<<bit);i++)w[depth[disty][i].S]=0;
        if (cur == dist )idy+=(1<<bit);
    }
    idy=depth[disty][idy+1].F;
 
 
    answer(idx,idy);
}
/*
signed main() {
    int n;
    cin>>n;
    vi V,U;
    for (int i=0;i<n-1;i++) {
        int u,v;
        cin>>u>>v;
        V.pb(v);
        U.pb(u);
    }
    int A,B;
    cin>>A>>B;
    find_pair(n,U,V,A,B);
}
*/

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if ( idx+(1<<bit) >= depth[distx].size() )continue;
      |              ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
highway.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         if ( idy+(1<<bit) >= depth[disty].size() )continue;
      |              ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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