제출 #236759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236759		lyc	통행료 (IOI18_highway)	C++14	100 / 100	313 ms	10988 KiB

highway

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

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> ii;

const int mxN = 90005;
const int mxM = 130005;
int N, M, A, B;
int E[mxM];
vector<int> al[mxN], num;
vector<ii> pa;

vector<int> w;
ll L;
int qcnt = 0;
bool query() { 
    ++qcnt;
    assert(qcnt <= 100);
    ll r = ask(w);
    //cout << qcnt << " :: ";
    //FOR(i,0,M-1) cout << w[i] << ' ';
    //cout << " :: " << r << endl;
    return r == L;
}

void bfs(vector<int> s) {
    int cnt = 0;
    num.assign(N,-1);
    pa.assign(N,ii(-1,-1));
    queue<int> q;
    for (auto& u : s) { num[u] = cnt++, pa[u].second = u, q.push(u); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int e : al[u]) {
            int v = E[e]^u;
            if (num[v] == -1) { num[v] = cnt++, pa[v] = ii(e,pa[u].second), q.push(v); }
        }
    }
}

void setW(vector<int>::iterator s, vector<int>::iterator e, int p) {
    vector<int> vis(N,0);
    for (auto it = s; it != e; ++it) {
        for (int x = *it; pa[x].first != -1 && !vis[x]; x = E[pa[x].first]^x) {
            vis[x] = 1;
            w[pa[x].first] = p;
        }
    }
}

int solve(int s) {
    vector<int> vtx;
    FOR(i,0,N-1) if (pa[i].second == s) vtx.push_back(i);
    sort(ALL(vtx),[](int a, int b) { return num[a] < num[b]; });
    //cout << "VTX: ";
    //for (auto& x : vtx) cout << x << ' ';
    //cout << endl;
    setW(ALL(vtx),1);
    int lo = -1, hi = SZ(vtx)-1;
    while (hi-lo > 1) {
        int mid = (lo+hi)/2;
        setW(vtx.begin(),vtx.begin()+mid+1,0);
        if (query()) hi = mid;
        else lo = mid;
        setW(vtx.begin(),vtx.begin()+mid+1,1);
    }
    setW(ALL(vtx),0);
    //TRACE(hi _ vtx[hi]);
    return vtx[hi];
}

void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) {
    N = _N;
    M = U.size();
    FOR(i,0,M-1){
        E[i] = U[i]^V[i];
        al[U[i]].push_back(i);
        al[V[i]].push_back(i);
    }
    A = _A, B = _B;

    w.assign(M,0);
    L = ask(w);

    int lo = -1, hi = M;
    while (hi-lo > 1) {
        int mid = (lo+hi)/2;
        FOR(i,lo+1,mid) w[i] = 1;
        if (query()) lo = mid;
        else {
            FOR(i,lo+1,mid) w[i] = 0;
            hi = mid;
        }
    }

    bfs({U[hi],V[hi]});
    w.assign(M,1);
    vector<int> vtx(N); iota(ALL(vtx),0);
    setW(ALL(vtx),0);
    w[hi] = 0;
    int S = solve(U[hi]), T = solve(V[hi]);
    //TRACE(S _ T);
    answer(S,T);
}

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