Submission #236723

#	Time	Username	Problem	Language	Result	Execution time	Memory
236723		lyc	Highway Tolls (IOI18_highway)	C++14	51 / 100	245 ms	9948 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;
int N, M, A, B;
int E[mxN];
vector<int> al[mxN];
vector<int> dist;
vector<ii> tree;
vector<int> w;

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

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

void setW(int u, int v, vector<int>& V, int p) {
    vector<bool> vis(N,0);
    FOR(i,u,v){
        for (int x = V[i]; tree[x].first != -1 && !vis[x]; x = E[tree[x].first]^x) {
            vis[x] = 1;
            w[tree[x].first] = p;
        }
    }
}

int solve(int S, int L, ll D) {
    w.assign(M,1);
    vector<int> V;
    FOR(i,0,N-1) if (tree[i].second == S && dist[i] == L) V.push_back(i);
    setW(0,SZ(V)-1,V,0);
    int lo = -1, hi = SZ(V)-1;
    while (hi-lo > 1) {
        int mid = (lo+hi)/2;
        setW(lo+1,mid,V,1);
        ll q = query();
        setW(lo+1,mid,V,0);
        if (q < D) lo = mid;
        else hi = mid;
    }
    return V[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);
    ll toll = query();
    int e;
    {
        int lo = -1, hi = M;
        while (hi-lo > 1) {
            int mid = (lo+hi)/2;
            FOR(i,lo+1,mid) w[i] = 1;
            ll q = query();
            if (q == toll) lo = mid;
            else {
                FOR(i,lo+1,mid) w[i] = 0;
                hi = mid;
            }
        }
        e = hi;
    }
    //TRACE(U[e] _ V[e]);

    bfs({U[e],V[e]});

    w.assign(M,0);
    vector<int> vec;
    FOR(i,0,N-1) if (tree[i].second == U[e]) vec.push_back(i);
    setW(0,SZ(vec)-1,vec,1);
    int l = toll / A;
    int l1 = (query() - toll) / (B - A);
    int l2 = l - 1 - l1;
    //TRACE(l1 _ l2);

    int S = solve(U[e],l1,(ll)l*B), T = solve(V[e],l2,(ll)l*B);
    //TRACE(S _ T);
    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