Submission #116160

#	Time	Username	Problem	Language	Result	Execution time	Memory
116160		RezwanArefin01	Highway Tolls (IOI18_highway)	C++17	51 / 100	325 ms	9980 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;
int l[MX], r[MX], a, b, n, m, comp[MX];
ll base0;

int findEdge() {
    int lo = 0, hi = m - 1, e;
    base0 = ask(q);

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

    return e;
}

void bfs(int root, vector<int> &d, int c, bool store = 0) {
    queue<int> Q; 
    d[root] = 0; 
    Q.push(root); 

    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int i : adj[u]) {
            int v = u ^ l[i] ^ r[i]; 
            if(comp[v] == c && d[v] == -1) {
                d[v] = d[u] + 1; 
                Q.push(v);
                if(store) t.push_back(i);
            }
        }
    }
}

int find(int c, vector<int> &d) {
    if(!t.size()) return -1; 

    sort(t.begin(), t.end(), [&](int i, int j) {
        return max(d[l[i]], d[r[i]]) < max(d[l[j]], d[r[j]]); 
    });

    q = vector<int> (m, 0);
    for(int i : t) q[i] = 1; 

    ll base = ask(q); 
    if(base == base0) return -1;

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

    return d[l[e]] > d[r[e]] ? l[e] : r[e];
}

void find_pair(int _n, vector<int> U, vector<int> V, int _a, int _b) {
    n = _n, a = _a, b = _b;
    m = U.size(); 
    copy(U.begin(), U.end(), l); 
    copy(V.begin(), V.end(), r); 

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

    int e = findEdge(); 

    vector<int> du (n, -1), dv (n, -1); 
    bfs(l[e], du, 0); 
    bfs(r[e], dv, 0); 

    for(int i = 0; i < n; ++i) {
        comp[i] = du[i] > dv[i];
    }   

    du = vector<int> (n, -1); 
    bfs(l[e], du, 0, 1); 
    int S = find(0, du); 

    t.clear(); 

    dv = vector<int> (n, -1);
    bfs(r[e], dv, 1, 1);
    int T = find(0, dv); 

    if(S == -1) S = l[e]; 
    if(T == -1) T = r[e];
    answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'int findEdge()':
highway.cpp:17:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 1; 
                   ~~~^~~~
highway.cpp: In function 'int find(int, std::vector<int>&)':
highway.cpp:61:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 1; 
                   ~~~^~~~
highway.cpp: In function 'int findEdge()':
highway.cpp:25:12: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return e;
            ^
highway.cpp: In function 'int find(int, std::vector<int>&)':
highway.cpp:70:27: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return d[l[e]] > d[r[e]] ? l[e] : r[e];
                        ~~~^

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