Submission #1124969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124969		Pacybwoah	Highway Tolls (IOI18_highway)	C++20	69 / 100	174 ms	13260 KiB

highway

#include "highway.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cassert>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
    int n, m;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
    n = N;
    m = (int)U.size();
    vector<vector<pair<int, int>>> graph(n);
    for(int i = 0; i < m; i++){
        graph[U[i]].emplace_back(V[i], i);
        graph[V[i]].emplace_back(U[i], i);
    }
    vector<int> que(m);
    ll len = ask(que);
    auto reset = [&](){
        for(int i = 0; i < m; i++) que[i] = 0;
    };
    int l = 0, r = m - 1;
    while(l < r){
        int mid = (l + r) >> 1;
        reset();
        for(int i = 0; i <= mid; i++) que[i] = 1;
        if(ask(que) != len) r = mid;
        else l = mid + 1;
    }
    int u = U[l], v = V[l];
    vector<int> disu(n, -1), disv(n, -1);
    vector<int> edu(n), edv(n);
    vector<bool> visu(m), visv(m);
    disu[u] = 0;
    disv[v] = 0;
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        int node = q.front();
        q.pop();
        for(auto &[x, eid]: graph[node]){
            if(disu[x] == -1){
                visu[eid] = 1;
                edu[x] = eid;
                disu[x] = disu[node] + 1;
                q.push(x);
            }
        }
    }
    q.push(v);
    while(!q.empty()){
        int node = q.front();
        q.pop();
        for(auto &[x, eid]: graph[node]){
            if(disv[x] == -1){
                visv[eid] = 1;
                edv[x] = eid;
                disv[x] = disv[node] + 1;
                q.push(x);
            }
        }
    }
    vector<pair<pair<int, int>, int>> bsu, bsv;
    for(int i = 0; i < n; i++){
        if(i == u) continue;
        if(disu[i] < disv[i]) bsu.push_back(make_pair(make_pair(disu[i], edu[i]), i));
        /*else if(disv[i] < disu[i]) *///bsv.push_back(make_pair(make_pair(disv[i], edv[i]), i));
        //cout << i << " " << disu[i] << " " << disv[i] << "\n";
    }
    fill(visv.begin(), visv.end(), 0);
    fill(edv.begin(), edv.end(), 0);
    fill(disv.begin(), disv.end(), -1);
    sort(bsu.begin(), bsu.end());
    sort(bsv.begin(), bsv.end());
    auto reset2 = [&](bool flag){
        for(int i = 0; i < m; i++){
            if(((!flag) && visu[i]) || (flag && visv[i])) que[i] = 0;
            else que[i] = 1;
        }
    };
    l = 0, r = (int)bsu.size();
    int sz = r;
    while(l < r){
        int mid = ((l + r) >> 1);
        reset2(0);
        for(int i = mid; i < sz; i++) que[bsu[i].first.second] = 1;
        if(ask(que) == len) r = mid;
        else l = mid + 1;
    }
    int s, t;
    if(l == 0) s = u;
    else s = bsu[l - 1].second;
    v = s;
    disv[v] = 0;
    q.push(v);
    while(!q.empty()){
        int node = q.front();
        q.pop();
        for(auto &[x, eid]: graph[node]){
            if(disv[x] == -1){
                visv[eid] = 1;
                edv[x] = eid;
                disv[x] = disv[node] + 1;
                q.push(x);
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(i == v) continue;
        /*if(disu[i] < disv[i]) *///bsu.push_back(make_pair(make_pair(disu[i], edu[i]), i));
        /*else if(disv[i] < disu[i]) */bsv.push_back(make_pair(make_pair(disv[i], edv[i]), i));
        //cout << i << " " << disu[i] << " " << disv[i] << "\n";
    }
    sort(bsv.begin(), bsv.end());
    l = 0, r = (int)bsv.size();
    sz = r;
    while(l < r){
        int mid = (l + r) >> 1;
        reset2(1);
        for(int i = mid; i < sz; i++) que[bsv[i].first.second] = 1;
        if(ask(que) == len) r = mid;
        else l = mid + 1;
    }
    if(l == 0) t = v;
    else t = bsv[l - 1].second;
    //cout << u << " " << v << " " << s << " " << t << "\n";
    //for(int i = 0; i < (int)bsu.size(); i++) cout << bsu[i].first.first << " " << bsu[i].first.second << " " << bsu[i].second << "\n";
    //for(int i = 0; i < (int)bsv.size(); i++) cout << bsv[i].first.first << " " << bsv[i].first.second << " " << bsv[i].second << "\n";
    answer(s, t);
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp highway.cpp

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