Submission #781424

#	Time	Username	Problem	Language	Result	Execution time	Memory
781424		vjudge1	Highway Tolls (IOI18_highway)	C++17	0 / 100	279 ms	262144 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> adj[100100];
int dep[100100], par[100100];
void dfs(int n, int p = -1, int d = 0) {
    dep[n] = d;
    for(auto i: adj[n])
        if(i.first!=p)
            dfs(i.first, n, d+1), par[i.first] = i.second;
}
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);
    int M = U.size();
    std::vector<int> w(M, 0);
    long long toll = ask(w);
    int dis = toll/A;
    vector<int> x;
    for(int i = 0; i < N; i++)
        if(dep[i]==dis)
            x.push_back(i);
    while(x.size() > 1) {
        vector<int> a,b,c(N-1,0);
        for(int i = 0; i < x.size()/2; i++) {
            a.push_back(x[i]);
            c[par[i]] = 1;
        }
        for(int i = x.size()/2; i < x.size(); i++) {
            b.push_back(x[i]);
        }
        if(ask(c)>toll)
            x = a;
        else 
            x = b;
    }
    answer(0, x[0]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i = 0; i < x.size()/2; i++) {
      |                        ~~^~~~~~~~~~~~
highway.cpp:30:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int i = x.size()/2; i < x.size(); i++) {
      |                                 ~~^~~~~~~~~~

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