Submission #139404

#	Time	Username	Problem	Language	Result	Execution time	Memory
139404		degelo	Highway Tolls (IOI18_highway)	C++17	12 / 100	430 ms	19584 KiB

highway

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

vector<int> cam;
int A,B;

vector<int> grafo[90004];
vector<int> ek,vk,teste;
map< pair<int,int> ,int > edge;
void dfs(int v,int p,int dist,int k){
    for(int i=0;i<grafo[v].size();i++){
        int viz=grafo[v][i];
        if(viz!=p){
            if(dist==k-1){
                ek.push_back(edge[make_pair(v,viz)]);
                vk.push_back(viz);
            }
            else{
                dfs(viz,v,dist+1,k);
            }
        }
    }
}
void paint(int ini,int fim){
    for(int i=0;i<teste.size();i++){
        teste[i]=0;
    }
    for(int i=ini;i<=fim;i++){
        teste[ek[i]]=1;
    }
}
/*void answer(int s,int t){
    cout<<s<<" "<<t<<endl;
}
long long int ask(vector<int> a){
    long long int resp=0;
    for(int i=0;i<cam.size();i++){
        if(a[cam[i]]==0) resp+=A;
        else resp+=B;
    }
    return resp;
}*/
void find_pair(int n,vector<int> u,vector<int> v,int a,int b){
    for(int i=0;i<u.size();i++){
        edge[make_pair(u[i],v[i])]=i;
        edge[make_pair(v[i],u[i])]=i;
        grafo[u[i]].push_back(v[i]);
        grafo[v[i]].push_back(u[i]);
        teste.push_back(0);
    }
    long long int t1=ask(teste);
    int k=t1/a;
    dfs(0,-1,0,k);
    /*for(int i=0;i<ek.size();i++){
        cout<<ek[i]<<" "<<vk[i]<<endl;

    }*/

    int ini=0,fim=ek.size()-1;
    while(ini!=fim){
        int meio=(fim+ini)/2;
        paint(ini,meio);
        long long int t=ask(teste);
        if(t==t1){
            ini=meio+1;
        }
        else{
            fim=meio;
        }
    }
    answer(0,vk[ini]);
}
/*int main(){
    int n,m;
    cin>>n>>m;
    vector<int> u,v;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        u.push_back(a);
        v.push_back(b);
    }
    int c;
    cin>>c;
    for(int i=0;i<c;i++){
        int a;
        cin>>a;
        cam.push_back(a);
    }
    cin>>A>>B;
    find_pair(n,u,v,A,B);
}*/

Compilation message (stderr)

highway.cpp: In function 'void dfs(int, int, int, int)':
highway.cpp:12:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<grafo[v].size();i++){
                 ~^~~~~~~~~~~~~~~~
highway.cpp: In function 'void paint(int, int)':
highway.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<teste.size();i++){
                 ~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<u.size();i++){
                 ~^~~~~~~~~

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