Submission #1241129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241129		Zbyszek99	통행료 (IOI18_highway)	C++20	18 / 100	130 ms	16896 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;

vector<pii> graph[90001];
vector<pii> dij_graph[90001];
bool odw[90001];
ll cost[130001];
bool is_take[130001];
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)
{
    forall(it,graph[v])
    {
        if(is_take[it.ff])
        {
            Q[it.ss] ^= 1;
            continue;
        }
        dfs(it.ff);
    }
}

void find_pair(int N, vi U, vi V, int A, int B) 
{
    n = N;
    int m = siz(U);
    vi W(m,1);
    ll base_toll = ask(W);
    ll tree_toll;
    int l = 0;
    int r = m-1;
    int edge = 0;
    while(l <= r)
    {
        int mid = (l+r)/2;
        rep(i,m) W[i] = 1;
        rep2(i,0,mid) W[i] = 0;
        ll new_toll = ask(W);
        if(new_toll != base_toll)
        {
            tree_toll = new_toll;
            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});
        cost[i] = A;
    }
    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});
        cost[i] = B;
    }
    priority_queue<pair<ll,pii>,vector<pair<ll,pii>>,greater<pair<ll,pii>>> pq;
    pq.push({0,{U[edge],-1}});
    pq.push({0,{V[edge],-1}});
    while(!pq.empty())
    {
        pair<ll,pii> t = pq.top();
        pq.pop();
        if(odw[t.ss.ff]) continue;
        odw[t.ss.ff] = 1;
        if(t.ss.ss != -1) 
        {
            if(U[t.ss.ss] == t.ss.ff) graph[V[t.ss.ss]].pb({t.ss.ff,t.ss.ss});
            else graph[U[t.ss.ss]].pb({t.ss.ff,t.ss.ss});
        }
        forall(it,dij_graph[t.ss.ff])
        {
            pq.push({t.ff+cost[it.ss],{it.ff,it.ss}});
        }
    }
    vi tree1;
    vi tree2;
    bfs(V[edge],tree1);
    bfs(U[edge],tree2);
    l = 0;
    r = siz(tree1)-1;
    int a;
    while(l <= r)
    {
        int mid = (l+r)/2;
        Q = W;
        rep(i,m) is_take[i] = 0;
        rep(i,mid+1) is_take[tree1[i]] = 1;
        dfs(tree1.back());
        if((mid != siz(tree1)-1 ? ask(Q) : -1) != tree_toll)
        {
            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;
        Q = W;
        rep(i,m) is_take[i] = 0;
        rep(i,mid+1) is_take[tree2[i]] = 1;
        dfs(tree2.back());
        if((mid != siz(tree2)-1 ? ask(Q) : -1) != tree_toll)
        {
            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: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31