Submission #1039485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039485		vjudge1	Highway Tolls (IOI18_highway)	C++17	12 / 100	222 ms	262144 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
int par[200100],dep[200100];
vector<pair<int,int>>adj[200100];
void dfs(int n,int p){
    for(auto [i,k]:adj[n])
        if(i-p)
            dep[i]=dep[n]+1,
            par[i]=k,dfs(i,n);
}
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);
    int D=ask(vector<int>(N-1,0))/A;
    vector<int>v;
    for(int i=1;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)==(long long)A*D)
            v=b;
        else v=a;
    }
    answer(0,v[0]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, 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++)
      |                     ~^~~~~~~~~

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