Submission #535427

#	Time	Username	Problem	Language	Result	Execution time	Memory
535427		mario05092929	Highway Tolls (IOI18_highway)	C++14	100 / 100	233 ms	11312 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
typedef vector <ll> vecl;
using namespace std;
const int INF = 1e9;
int n,m,p[100005],idx[100005];
vec v[100005];
vec w;
ll a,b,dist;
int d[2][100005],wh,c[100005];
vec num[2];
vector <pi> ed;

bool cmp(int x,int y) {
    return d[wh][x] < d[wh][y];
}

int Find_edge() {
    int l = 0,r = m-1;
    while(l < r) {
        int mid = (l + r) >> 1;
        w.clear(); w.resize(m,0);
        for(int i = 0;i <= mid;i++) w[i] = 1;
        if(ask(w) > dist) r = mid;
        else l = mid+1;
    }
    return l;
}

void BFS(int st,int no,int co) {
    queue <int> q; q.push(st);
    for(int i = 1;i <= n;i++) d[co][i] = INF;
    d[co][st] = 0;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i : v[x]) {
            if(d[co][i] == INF) {
                d[co][i] = d[co][x]+1;
                q.push(i);
            }
        }
    }
}

int Find(int co) {
    int l = 0,r = num[co].size()-1;
    int g = 1;
    memset(c,0,sizeof(c));
    while(l < r) {
        int mid = (l + r) >> 1;
        w.clear(); w.resize(m,0);
        for(int i = mid+1;i <= r;i++) c[num[co][i]] = g;
        for(int i = 0;i < m;i++) if(c[ed[i].x] == g||c[ed[i].y] == g) w[i] = 1;
        if(ask(w) > dist) l = mid+1;
        else r = mid;
        g++;
    }
    return num[co][l];
}

void find_pair(int N,vec U,vec V,int A,int B) {
    a = A, b = B;
    n = N, m = U.size();
    for(int i = 0;i < m;i++) {
        U[i]++, V[i]++;
        ed.push_back({U[i],V[i]});
        v[U[i]].push_back(V[i]);
        v[V[i]].push_back(U[i]);
    }
    dist = ask(vector<int>(m,0));
    int edge = Find_edge(),l = U[edge],r = V[edge];
    BFS(l,r,0), BFS(r,l,1);
    for(int i = 1;i <= n;i++) {
        if(d[0][i] < d[1][i]) num[0].push_back(i);
        else num[1].push_back(i);
    }
    sort(num[0].begin(),num[0].end(),cmp); wh = 1;
    sort(num[1].begin(),num[1].end(),cmp);
    answer(Find(0)-1,Find(1)-1);
}

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