제출 #405036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
405036		phathnv	통행료 (IOI18_highway)	C++11	0 / 100	23 ms	6372 KiB

highway

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

using namespace std;

const int MAXN = 90000;
const int MAXM = 130000;

int n, m, tIn[MAXN], timer, h[MAXN], cnt[MAXN];
vector<int> u, v, adj[MAXN];
long long allA;
bool mark[MAXM];

void BuildTree(int s) {
    timer = 0;
    for(int i = 0; i < n; i++){
        h[i] = -1;
        cnt[i] = 0;
    }
    queue<int> qu;
    h[s] = 0;
    tIn[s] = timer++;
    qu.push(s);
    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        cnt[h[u]]++;
        for(int ind : adj[u]) {
            if (mark[ind])
                continue;
            int v = ::u[ind] ^ ::v[ind] ^ u;
            if (h[v] == -1) {
                h[v] = h[u] + 1;
                tIn[v] = timer++;
                qu.push(v);
            }
        }
    }
    for(int i = 1; i < n; i++)
        cnt[i] += cnt[i - 1];
}

long long MyAsk(int l, int r) {
    vector<int> w(m);
    for(int i = 0; i < m; i++)
        if (mark[i] || (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(int l, int r) {
    assert(timer == n);
    int res = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (MyAsk(mid, n - 1) != allA) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    for(int i = 0; i < n; i++)
        if (tIn[i] == res)
            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();
    for(int i = 0; i < m; i++) {
        adj[u[i]].push_back(i);
        adj[v[i]].push_back(i);
    }
    iota(tIn, tIn + n, 0);
    timer = n;
    allA = MyAsk(-1, -1);
    int dist = allA / a;
    int root = Find_city(0, n - 1);
    for(int i = 0; i < m; i++)
        if ((root + 1 <= tIn[u[i]] && tIn[u[i]] <= n - 1) || (root + 1 <= tIn[v[i]] && tIn[v[i]] <= n - 1))
            mark[i] = 1;
    BuildTree(root);
    int s = Find_city(cnt[dist / 2], cnt[dist] - 1);
    BuildTree(s);
    int t = Find_city(cnt[dist - 1], cnt[dist] - 1);
    answer(s, t);
}

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