Submission #1210890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210890		garam1732	Highway Tolls (IOI18_highway)	C++20	0 / 100	9 ms	4180 KiB

highway

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*1;
const ll MOD = 998244353;
const ll INF = 1e16;

vector<pi> adj[MAXN];
vector<vector<int> > adj1, adj2;

queue<int> q;
vector<ll> d1, d2;
void bfs(int s, vector<ll> &d) {
    d[s] = 0; q.push(s);
    while(q.size()) {
        int here = q.front(); q.pop();

        for(auto [there,w] : adj[here]) {
            if(d[there] > d[here]+1) {
                d[there] = d[here]+1;
                q.push(there);
            }
        }
    }
} void bfs(int s, int t, vector<ll> &dst, vector<int>& v) {
    q.push(s);
    while(q.size()) {
        int here = q.front(); q.pop(); v.push_back(here);

        for(auto [there,w] : adj[here]) {
            if(dst[there] == dst[here]+1) {
                if(dst[there] < d2[there]+d1[there]-dst[there]) {
                    q.push(there);
                }
            }
        }
    }
}

bool chk[MAXN];
vector<int> v1, v2;
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int m = U.size();
    for(int i=0; i<m; i++) {
        adj[U[i]].push_back(pi(V[i], i));
        adj[V[i]].push_back(pi(U[i], i));
    }

    vector<int> w(m);
    ll len = ask(w)/A;
    int lb = 0, ub = m, mid;
    while(lb < ub) {
        mid = lb+ub>>1;
        for(int i=lb; i<=mid; i++) w[i] = 1;
        ll res = ask(w);

        if(res > A*len) {
            for(int i=lb; i<=mid; i++) w[i]=0;
            lb = mid+1;
        } else {
            ub = mid;
        }
    } int e = lb;

    int x = U[e], y = V[e];
    d1.resize(N, INF); d2.resize(N, INF);
    bfs(x, d1); bfs(y, d2);

    adj1.resize(N); adj2.resize(N);
    bfs(x, y, d1, v1); bfs(y, x, d2, v2);

    lb = 0, ub = (int)v1.size()-1, mid;
    while(lb < ub) {
        mid = lb+ub>>1;
        
        memset(chk, 0, sizeof chk);
        for(int i=0; i<=mid; i++) chk[v1[i]]=1;

        w.resize(m);
        for(int i=0; i<m; i++) {
            if(chk[U[i]]!=chk[V[i]]) w[i]=1;
        } ll res = ask(w);

        if(res == A*len) ub = mid;
        else lb = mid+1;
    } int p = v1[lb];

    lb = 0, ub = (int)v2.size()-1, mid;
    while(lb < ub) {
        mid = lb+ub>>1;
        
        memset(chk, 0, sizeof chk);
        for(int i=0; i<=mid; i++) chk[v2[i]]=1;

        w.resize(m);
        for(int i=0; i<m; i++) {
            if(chk[U[i]]!=chk[V[i]]) w[i]=1;
        } ll res = ask(w);

        if(res == A*len) ub = mid;
        else lb = mid+1;
    } int q = v2[lb];

	answer(p, q);
}

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