Submission #523754

#	Time	Username	Problem	Language	Result	Execution time	Memory
523754		InternetPerson10	Highway Tolls (IOI18_highway)	C++17	0 / 100	16 ms	2328 KiB

highway

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

using namespace std;
typedef long long ll;

pair<int, int> rootedTree(int N, vector<int> U, vector<int> V, int A, int B, ll dep = 0, int root = 0) { // tree, one is 0
    int M = U.size();
    vector<int> v(M, 1);
    if(dep == 0) dep = ask(v) / B;
    vector<vector<pair<int, int>>> adj(N);
    for(int i = 0; i < M; i++) {
        if(U[i] < 0) break;
        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, false);
    q.push({root, {root, -1}});
    while(q.size()) {
        auto p = q.front(); q.pop();
        taken[p.second.first] = true;
        if(p.first == dep) {
            candidates.push_back(p.second); 
            continue;
        }
        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 {root, candidates[ans].first};
}

pair<int, int> generalTree(int N, vector<int> U, vector<int> V, int A, int B) { // tree
    int M = U.size();
    vector<int> v(M, 1);
    vector<vector<pair<int, int>>> adj(N);
    vector<vector<pair<int, int>>> depths(N);
    for(int i = 0; i < M; i++) {
        if(U[i] < 0) break;
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    vector<bool> taken(N, false);
    queue<pair<int, pair<int, int>>> q;
    q.push({0, {0, -1}});
    while(q.size()) {
        auto p = q.front(); q.pop();
        taken[p.second.first] = true;
        depths[p.first].push_back(p.second);
        for(auto g : adj[p.second.first]) {
            if(taken[g.first]) continue;
            q.push({p.first + 1, g});
        }
    }
    while(depths.back().size() == 0) depths.pop_back();
    ll largeLength = ask(v);
    int l = 1, r = depths.size();
    while(l != r - 1) {
        int mid = (l + r) / 2;
        for(int i = mid; i < depths.size(); i++) {
            for(auto g : depths[i]) {
                v[g.second] = 0;
            }
        }
        if(ask(v) == largeLength) r = mid;
        else l = mid;
        for(int i = mid; i < depths.size(); i++) {
            for(auto g : depths[i]) {
                v[g.second] = 1;
            }
        }
    }
    int g = 0;
    while((1 << g) < depths[l].size()) g++;
    int ans = 0;
    for(int i = 0; i < g; i++) { // Funny way to divide people into two groups, check for good
        for(int j = 0; j < depths[l].size(); j++) {
            if((j ^ ans) % (1 << i)) continue;
            if(j & (1 << i)) v[depths[l][j].second] = 0;
        }
        if(ask(v) != largeLength) ans += (1 << i);
        for(int j = 0; j < depths[l].size(); j++) {
            if((j ^ ans) % (1 << i)) continue;
            if(j & (1 << i)) v[depths[l][j].second] = 1;
        }
    }
    return rootedTree(N, U, V, A, B, 0, ans);
}

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 = generalTree(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, ll, int)':
highway.cpp:34: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]
   34 |     while((1 << g) < candidates.size()) g++;
      |           ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
highway.cpp:37: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]
   37 |         for(int j = 0; j < candidates.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
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: In function 'std::pair<int, int> generalTree(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:75:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i = mid; i < depths.size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~
highway.cpp:82:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int i = mid; i < depths.size(); i++) {
      |                          ~~^~~~~~~~~~~~~~~
highway.cpp:89: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]
   89 |     while((1 << g) < depths[l].size()) g++;
      |           ~~~~~~~~~^~~~~~~~~~~~~~~~~~
highway.cpp:92: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]
   92 |         for(int j = 0; j < depths[l].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~
highway.cpp:97: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]
   97 |         for(int j = 0; j < depths[l].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:107:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |     if(U.size() + 1 == N) ans = generalTree(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