Submission #156491

#	Time	Username	Problem	Language	Result	Execution time	Memory
156491		rama_pang	Highway Tolls (IOI18_highway)	C++14	100 / 100	377 ms	12428 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e8;
const lint MAXN = 150005;
 
lint N, M, A, B;
vector<pair<int, int>> G[MAXN];
vector<int> LC, RC, color;
int S, T;

void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) {
    N = _N, A = _A, B = _B, M = U.size();
    for (int i = 0; i < M; i++) {
        G[U[i]].emplace_back(V[i], i);
        G[V[i]].emplace_back(U[i], i);
    }
    vector<int> guess(M, 0);
    lint D = ask(guess);
    lint le, ri, ans, check;
    /* find and edge e = uv, then construct tree rooted from u and from v */
    le = 0, ri = M - 1;
    while (le < ri) {
        lint mid = (le + ri) / 2;
        for (int i = 0; i < M; i++) guess[i] = i <= mid;
        if (ask(guess) != D) {
            ri = mid;                
        } else {
            le = mid + 1;
        }
    }
    ans = le;
    /* construct BFS tree */
    queue<int> q; q.push(U[ans]), q.push(V[ans]);
    color.assign(N, 0);
    color[U[ans]] = 1; color[V[ans]] = 2;
    LC.push_back(U[ans]); RC.push_back(V[ans]);

    vector<int> tt;
    tt.push_back(ans);
    while (!q.empty()) {
        int f = q.front(); q.pop();
        for (auto &g : G[f])  {
            int v = g.first, id = g.second;
            if (color[v] == 0) {
                if (color[f] == 1) {
                    color[v] = 1;
                    LC.push_back(v);
                } else {
                    color[v] = 2;
                    RC.push_back(v);
                }
                tt.push_back(id);
                q.push(v);
            }
        }
    }
    
    auto get = [&](vector<int> E) {
        le = 0, ri = E.size() - 1;
        while (le < ri) {
            int mid = (le + ri) / 2;
            vector<bool> cur(N);
            for (int i = mid + 1; i < E.size(); i++) {
                cur[E[i]] = true;
            }
            for (int i = 0; i < M; i++) {
                guess[i] = cur[U[i]] || cur[V[i]];
            }
            if (ask(guess) != D) {
                le = mid + 1;
            } else {
                ri = mid;
            }
        }
        return E[le];
    };

    answer(get(LC), get(RC));
}
 
/*
 
4 4 1 3 1 0
0 1
0 2
0 3
1 2
 
4 3 1 3 0 1
0 1
0 2
0 3
 
4 3 1 3 2 3
0 1
0 3
1 2
 
 
*/

Compilation message (stderr)

highway.cpp: In lambda function:
highway.cpp:65:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = mid + 1; i < E.size(); i++) {
                                   ~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:21:23: warning: unused variable 'check' [-Wunused-variable]
     lint le, ri, ans, check;
                       ^~~~~

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