Submission #116166

#	Time	Username	Problem	Language	Result	Execution time	Memory
116166		RezwanArefin01	Highway Tolls (IOI18_highway)	C++17	100 / 100	366 ms	9820 KiB

highway

#include <bits/stdc++.h>
using namespace std;
#include "highway.h"

typedef long long ll; 

const int MX = 9e4 + 5; 
vector<int> adj[MX], q, t[2];
int d[MX]; 
bool vis[MX]; 

void find_pair(int n, vector<int> l, vector<int> r, int a, int b) {
    int m = l.size(); 

    for(int i = 0; i < m; ++i) {
        adj[l[i]].push_back(i);
        adj[r[i]].push_back(i);
    }

    q = vector<int> (m, 0);
    ll base = ask(q); 

    int lo = 0, hi = m - 1, e;
    while(lo <= hi) {
        int mid = lo + hi >> 1; 
        for(int i = 0; i < m; ++i) 
            q[i] = i <= mid;
        if(ask(q) != base) 
            e = mid, hi = mid - 1; 
        else lo = mid + 1; 
    }

    int x = l[e], y = r[e]; 

    memset(d, 63, sizeof d);
    queue<pair<int, int>> Q; 
    d[x] = d[y] = 0;
    Q.emplace(x, 0); 
    Q.emplace(y, 1);

    while(!Q.empty()) {
        auto it = Q.front(); Q.pop();
        int u = it.first, c = it.second;
        t[c].push_back(u); 
        for(int i : adj[u]) {
            int v = u ^ l[i] ^ r[i]; 
            if(d[v] > d[u] + 1) {
                d[v] = d[u] + 1;
                Q.emplace(v, c); 
            }
        }
    }

    int S, T; 
    for(int i = 0; i < 2; ++i) {
        int sz = t[i].size(); 
        lo = 0, hi = sz - 1;
        while(lo <= hi) {
            int mid = lo + hi >> 1; 
            q = vector<int> (m, 0); 
            for(int j = mid + 1; j < sz; ++j) 
                vis[t[i][j]] = 1; 
            for(int i = 0; i < m; ++i) 
                if(vis[l[i]] || vis[r[i]]) 
                    q[i] = 1; 
            if(ask(q) == base) e = mid, hi = mid - 1; 
            else lo = mid + 1;
            for(int j = mid + 1; j < sz; ++j) 
                vis[t[i][j]] = 0; 
        }
        if(i) S = t[i][e]; 
        else T = t[i][e];
    }
    answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:25:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 1; 
                   ~~~^~~~
highway.cpp:59:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid = lo + hi >> 1; 
                       ~~~^~~~
highway.cpp:33:16: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x = l[e], y = r[e]; 
                ^

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