Submission #276010

#	Time	Username	Problem	Language	Result	Execution time	Memory
276010		doowey	Highway Tolls (IOI18_highway)	C++14	100 / 100	383 ms	13728 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

int n;
int m;

const int N = 130500;
int dis[2][N];
int par[2][N];

int c;
vector<pii> T[N];

void bfs(int u){
    dis[c][u]=0;
    par[c][u]=-1;
    queue<int> bf;
    bf.push(u);
    int node;
    while(!bf.empty()){
        node = bf.front();
        bf.pop();
        for(auto x : T[node]){
            if(dis[c][x.fi] > dis[c][node] + 1){
                dis[c][x.fi] = dis[c][node] + 1;
                par[c][x.fi] = x.se;
                bf.push(x.fi);
            }
        }
    }
    c ++ ;
}
struct Node{
    int dist;
    int parid;
    int ndx;
    bool operator<(const Node &F) const {
        return dist < F.dist;
    }
};


void find_pair(int _n, vector<int> u, vector<int> v, int a, int b) {
    n = _n;
    m = u.size();
    vector<int> w(m);
    for(int i = 0 ; i < m ; i ++ ){
        w[i] = 0;
        T[u[i]].push_back(mp(v[i], i));
        T[v[i]].push_back(mp(u[i], i));
    }
    ll dist = ask(w);
    int li = 0, ri = m-1;
    int mid;
    while(li < ri){
        mid = (li + ri) / 2;
        for(int j = 0 ; j < m ; j ++ ){
            if(j <= mid)
                w[j] = 0;
            else
                w[j] = 1;
        }
        if(ask(w) == dist)
            ri = mid;
        else
            li = mid + 1;
    }
    int p = u[li];
    int q = v[li];
    int man = li;
    for(int i = 0 ; i < 2; i ++ ){
        for(int j = 0 ; j < n; j ++ ){
            dis[i][j] = (int)1e9;
            par[i][j] = -1;
        }
    }
    bfs(p);
    bfs(q);
    vector<Node> cell[2];
    for(int i = 0 ; i < n; i ++ ){
        if(dis[0][i] == dis[1][i]){
            continue;
        }
        else if(dis[0][i] < dis[1][i]){
            cell[0].push_back({dis[0][i], par[0][i], i});
        }
        else{
            cell[1].push_back({dis[1][i], par[1][i], i});
        }
    }
    sort(cell[0].begin(), cell[0].end());
    sort(cell[1].begin(), cell[1].end());
    li = 0, ri = (int)cell[0].size() - 1;
    while(li < ri){
        mid = (li + ri) / 2;
        for(int i = 0 ; i < m ; i ++ ){
            w[i] = 1;
        }
        w[man] = 0;
        for(auto f : cell[1]){
            if(f.parid != -1){
                w[f.parid] = 0;
            }
        }
        for(int i = 0 ; i <= mid; i ++ ){
            if(cell[0][i].parid != -1)
                w[cell[0][i].parid] = 0;
        }
        if(ask(w) == dist)
            ri = mid;
        else
            li = mid + 1;
    }
    int S,T;
    S = cell[0][li].ndx;
    li = 0, ri = (int)cell[1].size() - 1;
    while(li < ri){
        mid = (li + ri) / 2;
        for(int i = 0 ; i < m; i ++ ){
            w[i] = 1;
        }
        w[man] = 0;
        for(auto f : cell[0]){
            if(f.parid != -1){
                w[f.parid] = 0;
            }
        }
        for(int i = 0 ; i <= mid; i ++ ){
            if(cell[1][i].parid != -1){
                w[cell[1][i].parid] = 0;
            }
        }
        if(ask(w) == dist)
            ri = mid;
        else
            li = mid + 1;
    }
    T = cell[1][li].ndx;
    answer(S,T);
}

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