Submission #744796

#	Time	Username	Problem	Language	Result	Execution time	Memory
744796		nguyentunglam	Highway Tolls (IOI18_highway)	C++17	100 / 100	257 ms	19744 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<pair<int, int>> adj[N];
vector<int> ke[N];
bool mark[N];
int n, m, par[N], st[N], cnt;
long long init;

void dfs(int u) {
    st[u] = ++cnt;
    for(int &v : ke[u]) dfs(v);
}

int Find(int s) {
    cnt = 0;
    for(int i = 0; i < n; i++) st[i] = 0;
    dfs(s);
//    for(int i = 0; i < n; i++) cout << st[i] << " "; cout << endl;
    int l = 1, r = cnt, ret = 1;
    while (l <= r) {
        int mid = l + r >> 1;
        vector<int> w(m);
        for(int i = 0; i < m; i++) w[i] = mark[i];
        for(int i = 0; i < n; i++) if (st[i] > mid) w[par[i]] = 1;
        if (ask(w) == init) {
            ret = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    for(int i = 0; i < n; i++) if (st[i] == ret) return i;
}
void find_pair(int _n, std::vector<int> u, std::vector<int> v, int a, int b) {
    m = u.size();
    n = _n;
    for(int i = 0; i < n; i++) adj[i].clear(), ke[i].clear();
    for(int i = 0; i < m; i++) {
        adj[u[i]].emplace_back(v[i], i);
        adj[v[i]].emplace_back(u[i], i);
    }

    vector<int> w(m);
    init = ask(w);
    int l = 0, r = m - 1, idx = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        for(int i = 0; i < m; i++) w[i] = 0;
        for(int i = 0; i <= mid; i++) w[i] = 1;
        if (ask(w) > init) idx = mid, r = mid - 1;
        else l = mid + 1;
    }

    for(int i = 0; i < m; i++) mark[i] = 1;
    for(int i = 0; i < n; i++) par[i] = -1;
    mark[idx] = 0;
    par[u[idx]] = par[v[idx]] = idx;
    queue<int> q;
    q.push(u[idx]); q.push(v[idx]);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for(auto &[v, i] : adj[u]) if (par[v] < 0) {
            par[v] = i; mark[i] = 0;
            ke[u].push_back(v);
            q.push(v);
        }
    }
    int res1 = Find(u[idx]), res2 = Find(v[idx]);
    answer(res1, res2);
}

Compilation message (stderr)

highway.cpp: In function 'int Find(int)':
highway.cpp:23:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         int mid = l + r >> 1;
      |                   ~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:48:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int mid = l + r >> 1;
      |                   ~~^~~
highway.cpp: In function 'int Find(int)':
highway.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^

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