Submission #369138

#	Time	Username	Problem	Language	Result	Execution time	Memory
369138		denkendoemeer	Highway Tolls (IOI18_highway)	C++14	51 / 100	224 ms	262148 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"
#define ll long long
using namespace std;
int ans[2];
vector<int>w;
vector<pair<int,int>>g[100005],vec;
void dfs(int nod,int t)
{
    for(auto it:g[nod]){
        if (it.first!=t){
            vec.push_back(it);
            dfs(it.first,nod);
        }
    }
}
int calc(ll sum,ll b)
{
    int st=0,dr=vec.size()-1,mij,i;
    while(st<dr){
        mij=(st+dr)/2;
        for(i=1;i<vec.size();i++)
            if (i<=mij)
                w[vec[i].second]=1;
            else
                w[vec[i].second]=0;
        if (ask(w)==sum*b)
            dr=mij;
        else
            st=mij+1;
    }
    return st;
}
void find_pair(int n,vector<int>u,vector<int>v,int a,int b)
{
    int m=u.size(),i;
    for(i=0;i<m;i++){
        g[u[i]].push_back(make_pair(v[i],i));
        g[v[i]].push_back(make_pair(u[i],i));
    }
    w.assign(m,0);
    ll sum=ask(w)/a;
    int root=0;
    for(i=0;i<2;i++){
        vec.clear();
        vec.push_back(make_pair(0,-1));
        dfs(root,-1);
        int nr=calc(sum,b);
        root=ans[i]=vec[nr].first;
    }
    answer(ans[0],ans[1]);
}

Compilation message (stderr)

highway.cpp: In function 'int calc(long long int, long long int)':
highway.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(i=1;i<vec.size();i++)
      |                 ~^~~~~~~~~~~

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