Submission #624155

#	Time	Username	Problem	Language	Result	Execution time	Memory
624155		Ronin13	Highway Tolls (IOI18_highway)	C++14	100 / 100	516 ms	50512 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int NMAX = 1e6 + 1;

vector <vector <int> > g(NMAX);

int D[NMAX][2];
vector <int> p(NMAX, -1);

int n;
ll a, b;
int d[NMAX][2];
ll sz1, sz2 = 0;

map<pii, bool> used1;
vector <bool> used(NMAX);

void bfs(int x, int y){
    queue <int> q;
    q.push(x);
    //cout << x << y;
    used1[{x, y}] = used1[{y, x}] = true;
    for(int i = 0; i < n; i++){
        D[i][0] = D[i][1] = 1e9;
        d[i][0] = d[i][1] = -1;
    }
    D[x][0] = 0;
    q.push(x);
    while(!q.empty()){
        int v = q.front();
       // cout << v << ' ';
        q.pop();
        for(int to : g[v]){
            if(D[to][0] > D[v][0] + 1){
                D[to][0] = D[v][0] + 1;
                q.push(to);
            }
        }
    }
    D[y][1] = 0;
    q.push(y);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int to : g[v]){
            if(D[to][1] > D[v][1] + 1){
                D[to][1] = D[v][1] + 1;
                q.push(to);
            }
        }
    }
    q.push(x);
    int cnt = 1;
    d[x][0] = 0;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int to : g[v]){
            if(D[to][0] < D[to][1]){
                if(d[to][0] == -1) {d[to][0] = cnt++, sz1++, used1[{v, to}] = used1[{to, v}] = true, q.push(to); }
            }
        }
    }
    q.push(y);
    cnt = 1;
    d[y][1] = 0;
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int to : g[v]){
            if(D[to][1] <= D[to][0]){
                if(d[to][1] == -1) d[to][1] = cnt++, sz2++, used1[{v, to}] = used1[{to, v}] = true, q.push(to);
            }
        }
    }
}



void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N;
    int m = U.size();
    for(int i = 0; i < m; i++){
        g[U[i]].pb(V[i]);
        g[V[i]].pb(U[i]);
    }
    ll a = A, b = B;
    vector <int> vec;
    vec.resize(m);
    const vector <int> v = vec;
    ll mn = ask(v);
    int l = -1, r = m;
    while(l + 1 < r){
        int mid = (l + r) / 2;
        vector <int> xx;
        for(int i = 0; i < m; i++){
            if(i <= mid) xx.pb(0);
            else xx.pb(1);
        }
        const vector <int> vv = xx;
        ll x = ask(vv);
        if(x == mn) r = mid;
        else l = mid;
    }
  //  cout << r << "\n";
    int x = U[r], y = V[r];
    bfs(x, y);
    for(int i = 0; i < m; i++){
        if(used1[{U[i], V[i]}]) used[i] = true;
    }

    l = -1, r = sz1 + 1;
    while(l + 1 < r){
        int mid = (l + r) / 2;
        vector <int> xx;
        for(int i = 0; i < m; i++){
            int u = U[i], v = V[i];
            if(!used[i]) xx.pb(1);
            else{
                if(d[u][0] <= mid && d[v][0] <= mid) xx.pb(0);
                else xx.pb(1);
            }
        }
        const vector <int> vv = xx;
        ll x = ask(vv);
        if(x == mn) r = mid;
        else l = mid;
    }
    int s;
    for(int i = 0; i < n; i++) if(d[i][0] == r) {s = i; break;}
    //cout << s << "\n";
    l = -1, r = sz2;
    while(l + 1 < r){
        int mid = (l + r) / 2;
        vector <int> xx;
        for(int i = 0; i < m; i++){
            int u = U[i], v = V[i];
            if(!used[i]) xx.pb(1);
            else{
                if(d[u][1] <= mid && d[v][1] <= mid) xx.pb(0);
                else xx.pb(1);
            }
        }
        const vector <int> vv = xx;
        ll x = ask(vv);
        if(x == mn) r = mid;
        else l = mid;
    }
    //cout << r;
    int t;
    for(int i = 0; i < n; i++) if(d[i][1] == r) {t = i; break;}
    answer(s, t);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:96:8: warning: unused variable 'a' [-Wunused-variable]
   96 |     ll a = A, b = B;
      |        ^
highway.cpp:96:15: warning: unused variable 'b' [-Wunused-variable]
   96 |     ll a = A, b = B;
      |               ^
highway.cpp:161:11: warning: 'second' may be used uninitialized in this function [-Wmaybe-uninitialized]
  161 |     answer(s, t);
      |     ~~~~~~^~~~~~
highway.cpp:161:11: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]

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