Submission #1039490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039490		vjudge1	Highway Tolls (IOI18_highway)	C++17	51 / 100	96 ms	36192 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
#define M 1<<17
using namespace std;
int par[M],dep[M],ord[M],pos[M],CC;
vector<pair<int,int>>adj[M];
void dfs(int n,int p){
    ord[pos[n]=++CC]=n;
    for(auto [i,k]:adj[n])
        if(i-p)
            dep[i]=dep[n]+1,
            par[i]=k,dfs(i,n);
}
void doanswer(int endpt,int N,int A,int B,long long D){
    CC=0;
    dep[endpt]=0;
    dfs(endpt,-1);
    vector<int>v;
    for(int i=0;i<N;i++)
        if(dep[i]==D)
            v.push_back(i);
    while(v.size()>1){
        vector<int>a,b;
        for(int i=0;i<v.size();i++)
            if(i%2)a.push_back(v[i]);
            else b.push_back(v[i]);
        vector<int>edg(N-1);
        for(auto i:a)
            edg[par[i]]=1;
        if(ask(edg)==A*D)
            v=b;
        else v=a;
    }
    answer(endpt,v[0]);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    for(int i=0;i<N-1;i++)
        adj[U[i]].push_back({V[i],i}),
        adj[V[i]].push_back({U[i],i});
    dfs(0,0);
    long long D=ask(vector<int>(N-1,0))/A;
    int res=1e9,l=2,r=N;
    while(l<=r){
        int mid=l+r>>1;
        vector<int>v(N-1);
        for(int i=2;i<=mid;i++)
            v[par[ord[i]]]=1;
        if(ask(v)<D*B)
            l=mid+1;
        else res=mid,r=mid-1;
    }
    doanswer(ord[res],N,A,B,D);
}

Compilation message (stderr)

highway.cpp: In function 'void doanswer(int, int, int, int, long long int)':
highway.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i=0;i<v.size();i++)
      |                     ~^~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid=l+r>>1;
      |                 ~^~

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