Submission #523331

#	Time	Username	Problem	Language	Result	Execution time	Memory
523331		InternetPerson10	Highway Tolls (IOI18_highway)	C++17	0 / 100	13 ms	980 KiB

highway

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

using namespace std;
typedef long long ll;

pair<int, int> generalTree(int N, vector<int> U, vector<int> V, int A, int B) { // tree
    return {0, 0}; 
}

pair<int, int> rootedTree(int N, vector<int> U, vector<int> V, int A, int B) { // tree, one is 0
    int M = U.size();
    vector<int> v(M, 1);
    ll dep = ask(v) / B;
    vector<vector<pair<int, int>>> adj(N);
    for(int i = 0; i < M; i++) {
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    queue<pair<int, pair<int, int>>> q;
    vector<pair<int, int>> candidates;
    vector<bool> taken(N);
    q.push({0, {0, -1}});
    while(q.size()) {
        auto p = q.front(); q.pop();
        cout << p.first << '\n';
        taken[p.first] = true;
        if(p.first == dep) {
            candidates.push_back(p.second); 
            break;
        }
        for(auto g : adj[p.second.first]) {
            if(taken[g.first]) continue;
            q.push({p.first + 1, g});
        }
    }
    int g = 1;
    while((1 << g) < candidates.size()) g++;
    ll ans = 0;
    for(int i = 0; i < g; i++) {
        for(int j = 0; j < candidates.size(); j++) {
            if(j & (1 << i)) v[candidates[j].second] = 0;
        }
        if(ask(v) != dep * B) ans += (1 << i);
        for(int j = 0; j < candidates.size(); j++) {
            v[candidates[j].second] = 1;
        }
    }
    return {0, candidates[ans].first};
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    pair<int, int> ans;
    if(U.size() + 1 == N) ans = rootedTree(N, U, V, A, B);    
    else {

    }
    answer(ans.first, ans.second);
}

Compilation message (stderr)

highway.cpp: In function 'std::pair<int, int> rootedTree(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while((1 << g) < candidates.size()) g++;
      |           ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
highway.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int j = 0; j < candidates.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
highway.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j = 0; j < candidates.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:54:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     if(U.size() + 1 == N) ans = rootedTree(N, U, V, A, B);
      |        ~~~~~~~~~~~~~^~~~

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