Submission #76994

#	Time	Username	Problem	Language	Result	Execution time	Memory
76994		someone_aa	Highway Tolls (IOI18_highway)	C++17	0 / 100	30 ms	3772 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
int n, m;
vector<int>w;
vector<pair<int,int> > g[maxn];

int dist[maxn][2], parent[maxn][2];
bool visited[maxn];

ll dista;

void bfs(int st, int d) {
    memset(visited,false,sizeof(visited));
    queue<int>q;
    q.push(st);

    parent[st][d] = -1;
    visited[st] = true;

    while(!q.empty()) {
        int curr = q.front();
        q.pop();

        for(auto i:g[curr]) {
            if(!visited[i.first]) {
                visited[i.first] = true;
                dist[i.first][d] = dist[curr][d] + 1;
                parent[i.first][d] = i.second;
                q.push(i.first);
            }
        }
    }
}

int solve(vector<int> x, int d) {
    vector<int>w;
    for(int i=0;i<m;i++) w.pb(0);
    vector<pair<int,int> > dists;
    for(int i:x) {
        dists.pb(mp(dist[i][d], i));
    }
    sort(dists.begin(), dists.end());

    //cout<<d<<": ";
    //for(int i:x) cout<<i<<" ";
    //cout<<"\n";
    for(int i=0;i<m;i++) w[i] = 1;
    for(int i:x) if(parent[i][d] != -1) w[parent[i][d]] = 0;

    /*cout<<d<<":\n";
    for(auto i:dists) {
        cout<<i.first<<" "<<i.second<<"\n";
    }*/

    ll dista = ask(w);
    int li=0, ri=dists.size()-1;
    while(li<ri) {
        int mid = (li+ri)/2;

        for(int i=li;i<=mid;i++) {
            if(parent[dists[i].second][d] != -1)
                w[parent[dists[i].second][d]] = 1;
        }
        ll distb = ask(w);

        for(int i=li;i<=mid;i++) {
            if(parent[dists[i].second][d] != -1)
                w[parent[dists[i].second][d]] = 0;
        }

        if(dista != distb) {
            ri = mid;
        }
        else {
            li = mid + 1;
        }
    }
    return dists[li].second;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N; m = U.size();
    int li=0, ri=m-1;

    for(int i=0;i<m;i++) {
        g[U[i]].pb(mp(V[i], i));
        g[V[i]].pb(mp(U[i], i));
    }

    for(int i=0;i<m;i++) w.pb(0);
    dista = ask(w);

    while(li<ri) {
        int mid = (li+ri)/2;
        for(int i=li;i<=mid;i++) {
            w[i] = 1;
        }
        ll distb = ask(w);
        for(int i=li;i<=mid;i++) {
            w[i] = 0;
        }
        if(dista == distb) {
            li = mid + 1;
        }
        else {
            ri = mid;
        }
    }
    int x = li;
    int u = U[x], v = V[x];
    bfs(u, 0);
    bfs(v, 1);

    vector<int>su, sv;
    for(int i=0;i<n;i++) {
        if(dist[i][0] <= dist[i][1]) {
            su.pb(i);
        }
        else {
            sv.pb(i);
        }
    }

    //cerr<<u<<" "<<v<<"\n";

    int xx = solve(su, 0);
    int yy = solve(sv, 1);
    //cout<<xx<<" "<<yy<<"\n";
    answer(xx, yy);
}

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