Submission #404950

#	Time	Username	Problem	Language	Result	Execution time	Memory
404950		phathnv	Highway Tolls (IOI18_highway)	C++11	51 / 100	214 ms	10136 KiB

highway

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

using namespace std;

const int MAXN = 90000;

int n, m, tIn[MAXN], timer;
vector<int> u, v, adj[MAXN];

void Dfs(int u, int p) {
    tIn[u] = timer++;
    for(int v : adj[u])
        if (v != p)
            Dfs(v, u);
}

long long MyAsk(int l, int r){
    vector<int> w(m);
    for(int i = 0; i < m; i++)
        if ((l <= tIn[u[i]] && tIn[u[i]] <= r) || (l <= tIn[v[i]] && tIn[v[i]] <= r))
            w[i] = 1;
        else
            w[i] = 0;
    return ask(w);
}

int Find_city() {
    assert(timer == n);
    long long allA = MyAsk(-1, -1);
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (MyAsk(mid + 1, r) != allA)
            l = mid + 1;
        else
            r = mid;
    }
    for(int i = 0; i < n; i++)
        if (tIn[i] == l)
            return i;
    assert(0);
}

void find_pair(int _n, vector<int> _u, vector<int> _v, int a, int b) {
    n = _n;
    u = _u;
    v = _v;
    m = u.size();
    assert(m == n - 1);
    for(int i = 0; i < m; i++) {
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    timer = 0;
    Dfs(0, -1);
    int s = Find_city();
    timer = 0;
    Dfs(s, -1);
    int t = Find_city();
    answer(s, t);
}

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