Submission #1077895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077895		vladilius	Highway Tolls (IOI18_highway)	C++17	0 / 100	3054 ms	20916 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert

void find_pair(int n, vector<int> U, vector<int> V, int A, int B){
    if (U.size() != (n - 1)){
        answer(0, 0);
        return;
    }
    vector<pii> g[n + 1];
    for (int i = 0; i < n - 1; i++){
        U[i]++; V[i]++;
        g[U[i]].pb({V[i], i});
        g[V[i]].pb({U[i], i});
    }
    
    vector<int> w(n - 1);
    ll nl = ask(w);
    
    auto em = [&](){
        fill(w.begin(), w.end(), 0);
    };
    
    vector<int> all;
    for (int i = 0; i < n - 1; i++) all.pb(i);
    
    while (all.size() > 1){
        int m = (int) (all.size()) / 2;
        em();
        for (int i = 0; i < m; i++){
            w[all[i]] = 1;
        }
        
        ll g = ask(w);
        if (g == nl){
            reverse(all.begin(), all.end());
            m = (int) all.size() - m;
            while (m--) all.pop_back();
        }
        else {
            while (all.size() > m) all.pop_back();
        }
    }
    
    int T = all[0], x = U[T], y = V[T];
    
    vector<int> d(n + 1), p(n + 1), pe(n + 1);
    function<void(int, int, int, vector<pii>&, vector<int>&)> dfs = [&](int v, int pr, int ed, vector<pii>& k, vector<int>& t){
        t.pb(v);
        p[v] = pr; pe[v] = ed;
        if (ed != -1) k.pb({pr, ed});
        for (auto [i, j]: g[v]){
            if (i == pr || j == T) continue;
            d[i] = d[v] + 1;
            dfs(i, v, j, k, t);
        }
    };
    
    vector<pii> c1, c2;
    vector<int> q1, q2;
    d[x] = d[y] = 0;
    dfs(x, 0, -1, c1, q1);
    dfs(y, 0, -1, c2, q2);
    
    auto add = [&](int v){
        while (v > 0){
            w[pe[v]] = 1;
            v = p[v];
        }
    };
    
    nl /= A;
    
    auto solve = [&](vector<pii> t1, vector<pii> t2, vector<int> q){
        em();
        for (auto [i, j]: t2) w[j] = 1;
        int dd = (int) (ask(w) - B * (nl - 1) - A) / (A - B);

        vector<int> all;
        for (int i: q){
            if (d[i] == dd){
                all.pb(i);
            }
        }
        
        if (all.empty()){
            while (true){
                n++;
            }
        }
        
        while (all.size() > 1){
            int m = (int) (all.size()) / 2;
            em();
            for (int i = 0; i < m; i++){
                add(all[i]);
            }
            
            ll S = ask(w);
            if (S == (1LL * B * dd + 1LL * A * (nl - dd))){
                while (all.size() > m) all.pop_back();
            }
            else {
                reverse(all.begin(), all.end());
                m = (int) all.size() - m;
                while (all.size() > m) all.pop_back();
            }
        }
        
        return (all[0] - 1);
    };
    
    answer(solve(c1, c2, q1), solve(c2, c1, q2));
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:12:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |     if (U.size() != (n - 1)){
      |         ~~~~~~~~~^~~~~~~~~~
highway.cpp:47:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |             while (all.size() > m) all.pop_back();
      |                    ~~~~~~~~~~~^~~
highway.cpp: In lambda function:
highway.cpp:107:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |                 while (all.size() > m) all.pop_back();
      |                        ~~~~~~~~~~~^~~
highway.cpp:112:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |                 while (all.size() > m) all.pop_back();
      |                        ~~~~~~~~~~~^~~

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