Submission #1241171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241171		Zbyszek99	Highway Tolls (IOI18_highway)	C++20	100 / 100	130 ms	14848 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<long long>
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int maxn = 90001;
vector<pii> graph[maxn];
vector<pii> dij_graph[maxn];
bool odw[maxn];
bool is_take[maxn];
int n;
vi Q;

void bfs(int v, vi& ans)
{
    queue<int> q;
    q.push(v);
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        ans.pb(t);
        forall(it,graph[t])
        {
            q.push(it.ff);
        }
    }
    reverse(all(ans));
}

void dfs(int v)
{
    stack<int> st;
    st.push(v);
    while(!st.empty())
    {
        int t = st.top();
        st.pop();
        forall(it,graph[t])
        {
            if(is_take[it.ff])
            {
                Q[it.ss] = 1;
                continue;
            }
            st.push(it.ff);
        }    
    }
}

void find_pair(int N, vi U, vi V, int X, int Y) 
{
    ll A = X;
    ll B = Y;
    n = N;
    int m = siz(U);
    vi W(m,1);
    ll dist = ask(W)/B;
    int l = 0;
    int r = m-1;
    int edge = 0;
    while(l <= r)
    {
        int mid = (l+r)/2;
        rep(i,m) W[i] = 0;
        rep2(i,0,mid) W[i] = 1;
        ll new_toll = ask(W);
        if(new_toll != dist*A)
        {
            edge = mid;
            r = mid-1;
        } 
        else
        {
            l = mid+1;
        }
    }
    rep2(i,0,edge)
    {
        W[i] = 0;
        dij_graph[U[i]].pb({V[i],i});
        dij_graph[V[i]].pb({U[i],i});
    }
    rep2(i,edge+1,m-1)
    {
        W[i] = 1;
        dij_graph[U[i]].pb({V[i],i});
        dij_graph[V[i]].pb({U[i],i});
    }
    queue<pii> pq;
    pq.push({U[edge],-1});
    pq.push({V[edge],-1});
    vi trees = {edge};
    while(!pq.empty())
    {
        pii t = pq.front();
        pq.pop();
        if(odw[t.ff]) continue;
        odw[t.ff] = 1;
        if(t.ss != -1) 
        {
            trees.pb(t.ss);
            if(U[t.ss] == t.ff) graph[V[t.ss]].pb({t.ff,t.ss});
            else graph[U[t.ss]].pb({t.ff,t.ss});
        }
        forall(it,dij_graph[t.ff])
        {
            pq.push(it);
        }
    }
    vi tree1;
    vi tree2;
    bfs(V[edge],tree1);
    bfs(U[edge],tree2);
    l = 0;
    r = siz(tree1)-1;
    int a;
    Q.resize(m);
    while(l <= r)
    {
        int mid = (l+r)/2;
        rep(i,m) Q[i] = 1;
        forall(it,trees) Q[it] = 0;
        rep(i,n) is_take[i] = 0;
        rep(i,mid+1) is_take[tree1[i]] = 1;
        dfs(tree1.back());
        if((mid != siz(tree1)-1 ? ask(Q) : -1) != A * dist)
        {
            a = tree1[mid];
            r = mid-1; 
        }
        else
        {
            l = mid+1;
        }
    }
    l = 0;
    r = siz(tree2)-1;
    int b;
    while(l <= r)
    {
        int mid = (l+r)/2;
        rep(i,m) Q[i] = 1;
        forall(it,trees) Q[it] = 0;
        rep(i,n) is_take[i] = 0;
        rep(i,mid+1) is_take[tree2[i]] = 1;
        dfs(tree2.back());
        if((mid != siz(tree2)-1 ? ask(Q) : -1) != A * dist)
        {
            b = tree2[mid];
            r = mid-1; 
        }
        else
        {
            l = mid+1;
        }
    }
    answer(a,b);
}

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