Submission #1158941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158941		PagodePaiva	Highway Tolls (IOI18_highway)	C++17	Compilation error	0 ms	0 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
#define ll long long

using namespace std;

const ll N = 90010;
vector <pair <ll, ll>> g[N];
pair <ll, ll> especial;
vector <ll> query;
pair <ll, ll> pai[N];
ll h[N];
ll t1;
vector <array <ll, 3>> arestas;

void dfs(ll v, ll p){
    for(auto [x, idx] : g[v]){
        if(x == p) continue;
        query[idx] = 1;
        dfs(x, v);
    }
    return;
}

void dfs2(ll v, ll p){
    for(auto [x, idx] : g[v]){
        if(x == p) continue;
        h[x] = h[v]+1;
        pai[x] = {v, idx};
        if(h[x] == t1) arestas.push_back({x, v, idx});
        dfs2(x, v);
    }
    return;
}

void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B) {
    ll m = u.size();
    for(ll i = 0;i < m;i++){
        ll a = u[i], b = v[i];
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    for(ll i = 0;i < m;i++){
        query.push_back(0);
    }
    ll h = ask(query)/A;
    ll l = 0, r = m-1;
    while(l < r){
        ll mid = (l+r)/2;
        for(ll i = l;i <= mid;i++){
            query[i] = 1;
        }
        ll t = ask(query);
        for(ll i = l;i <= mid;i++){
            query[i] = 0;
        }
        if(t > h*A){
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    especial = {u[l], v[l]};
    dfs(u[l], v[l]);
    // cout << u[l] << ' ' << v[l] << endl;
    ll S = ask(query);
    t1 = (S-A*h)/(B-A);
    //// cout << t1 << endl;
    ll ll = l;
    for(ll i = 0;i < m;i++){
        query[i] = 0;
    }
    pair <ll, ll> resposta;
    if(t1 == 0) resposta.first = u[ll];
    else{
        dfs2(u[ll], v[ll]);
        l = 0; r = arestas.size()-1;
        // cout << t1 << endl;
        for(auto [a, b, c] : arestas){
            // cout << a << ' ' << b << ' ' << c << endl;
        }
        while(l < r){
            ll mid = (l+r)/2;
            for(ll i = l;i <= mid;i++){
                query[arestas[i][2]] = 1;
            }
            ll t = ask(query);
            for(ll i = l;i <= mid;i++){
                query[arestas[i][2]] = 0;
            }
            // cout << t << endl;
            if(t > h*A){
                r = mid;
            }
            else{
                l = mid+1;
            }
        }
        resposta.first = arestas[l][0];
    }
    //// cout << resposta.first << endl;
    arestas.clear();
    t1 = h-t1-1;
    swap(u[ll], v[ll]);
    // cout << u[ll] << ' ' << v[ll] << endl;
    if(t1 == 0) resposta.second = u[ll];
    else{
        dfs2(u[ll], v[ll]);
        l = 0; r = arestas.size()-1;
        while(l < r){
            ll mid = (l+r)/2;
            for(ll i = l;i <= mid;i++){
                query[arestas[i][2]] = 1;
            }
            ll t = ask(query);
            for(ll i = l;i <= mid;i++){
                query[arestas[i][2]] = 0;
            }
            if(t > h*A){
                r = mid;
            }
            else{
                l = mid+1;
            }
        }
        resposta.second = arestas[l][0];
    }
    // cout << resposta.first << ' ' << resposta.second << endl;
    answer(resposta.first, resposta.second);
    return;
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:46:16: error: invalid initialization of reference of type 'const std::vector<int>&' from expression of type 'std::vector<long long int>'
   46 |     ll h = ask(query)/A;
      |                ^~~~~
In file included from highway.cpp:1:
highway.h:7:39: note: in passing argument 1 of 'long long int ask(const std::vector<int>&)'
    7 | long long ask(const std::vector<int> &w);
      |               ~~~~~~~~~~~~~~~~~~~~~~~~^
highway.cpp:53:20: error: invalid initialization of reference of type 'const std::vector<int>&' from expression of type 'std::vector<long long int>'
   53 |         ll t = ask(query);
      |                    ^~~~~
In file included from highway.cpp:1:
highway.h:7:39: note: in passing argument 1 of 'long long int ask(const std::vector<int>&)'
    7 | long long ask(const std::vector<int> &w);
      |               ~~~~~~~~~~~~~~~~~~~~~~~~^
highway.cpp:67:16: error: invalid initialization of reference of type 'const std::vector<int>&' from expression of type 'std::vector<long long int>'
   67 |     ll S = ask(query);
      |                ^~~~~
In file included from highway.cpp:1:
highway.h:7:39: note: in passing argument 1 of 'long long int ask(const std::vector<int>&)'
    7 | long long ask(const std::vector<int> &w);
      |               ~~~~~~~~~~~~~~~~~~~~~~~~^
highway.cpp:3:12: error: 'long long long' is too long for GCC
    3 | #define ll long long
      |            ^~~~
highway.cpp:70:8: note: in expansion of macro 'll'
   70 |     ll ll = l;
      |        ^~
highway.cpp:3:17: error: 'long long long' is too long for GCC
    3 | #define ll long long
      |                 ^~~~
highway.cpp:70:8: note: in expansion of macro 'll'
   70 |     ll ll = l;
      |        ^~
highway.cpp:70:11: error: expected unqualified-id before '=' token
   70 |     ll ll = l;
      |           ^
highway.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
highway.cpp:75:36: note: in expansion of macro 'll'
   75 |     if(t1 == 0) resposta.first = u[ll];
      |                                    ^~
highway.cpp:75:36: error: expected ']' before 'long'
   75 |     if(t1 == 0) resposta.first = u[ll];
      |                                    ^
      |                                    ]
highway.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
highway.cpp:77:16: note: in expansion of macro 'll'
   77 |         dfs2(u[ll], v[ll]);
      |                ^~
highway.cpp:77:16: error: expected ']' before 'long'
   77 |         dfs2(u[ll], v[ll]);
      |                ^
      |                ]
highway.cpp:88:24: error: invalid initialization of reference of type 'const std::vector<int>&' from expression of type 'std::vector<long long int>'
   88 |             ll t = ask(query);
      |                        ^~~~~
In file included from highway.cpp:1:
highway.h:7:39: note: in passing argument 1 of 'long long int ask(const std::vector<int>&)'
    7 | long long ask(const std::vector<int> &w);
      |               ~~~~~~~~~~~~~~~~~~~~~~~~^
highway.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
highway.cpp:105:12: note: in expansion of macro 'll'
  105 |     swap(u[ll], v[ll]);
      |            ^~
highway.cpp:105:12: error: expected ']' before 'long'
  105 |     swap(u[ll], v[ll]);
      |            ^
      |            ]
highway.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
highway.cpp:107:37: note: in expansion of macro 'll'
  107 |     if(t1 == 0) resposta.second = u[ll];
      |                                     ^~
highway.cpp:107:37: error: expected ']' before 'long'
  107 |     if(t1 == 0) resposta.second = u[ll];
      |                                     ^
      |                                     ]
highway.cpp:3:12: error: expected primary-expression before 'long'
    3 | #define ll long long
      |            ^~~~
highway.cpp:109:16: note: in expansion of macro 'll'
  109 |         dfs2(u[ll], v[ll]);
      |                ^~
highway.cpp:109:16: error: expected ']' before 'long'
  109 |         dfs2(u[ll], v[ll]);
      |                ^
      |                ]
highway.cpp:116:24: error: invalid initialization of reference of type 'const std::vector<int>&' from expression of type 'std::vector<long long int>'
  116 |             ll t = ask(query);
      |                        ^~~~~
In file included from highway.cpp:1:
highway.h:7:39: note: in passing argument 1 of 'long long int ask(const std::vector<int>&)'
    7 | long long ask(const std::vector<int> &w);
      |               ~~~~~~~~~~~~~~~~~~~~~~~~^