Submission #416164

#	Time	Username	Problem	Language	Result	Execution time	Memory
416164		2fat2code	Highway Tolls (IOI18_highway)	C++17	100 / 100	260 ms	12964 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

const int nmax = 90005;
const int mmax = 130005;

long long len_edges, a, b;
int N, M, goodedge;

vector<pair<int,int>>nod[nmax];

int find_lenght(int A, int B){
    vector<int>w;
    for(int i=0;i<M;i++) w.push_back(0);
    long long lmao = ask(w);
    return lmao / A;
}

int find_index(){
    int l = 0, r = M - 1, ok = 0;
    while(l <= r){
        int mid = l + (r - l) / 2;
        vector<int>w;
        for(int i=0;i<mid;i++) w.push_back(0);
        for(int i=mid;i<M;i++) w.push_back(1);
        long long lmao = ask(w);
        if(lmao > len_edges * a){
            ok = mid;
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    return ok;
}

vector<int> bfs(int vertex1, int vertex2, vector<int>U, vector<int>V){
    int marked[M], marked2[M];
    for(int i=0;i<M;i++) marked2[i] = 0;
    queue<int>Q;
    vector<int>interesting_egdes1, interesting_egdes2;
    int marked_v[N], viz[N], par[N];
    for(int i=0;i<N;i++){
        marked_v[i] = 0;
        viz[i] = 0;
        par[i] = 0;
    }
    par[vertex1] = -1;
    Q.push(vertex1);
    viz[vertex1] = 1;
    Q.push(vertex2);
    viz[vertex2] = 1;
    marked2[goodedge] = 1;
    marked_v[vertex2] = 1;
    while(Q.size()){
        int x = Q.front();
        Q.pop();
        for(auto it : nod[x]){
            if(!viz[it.fr]){
                if(marked_v[x] == 0){
                    interesting_egdes1.push_back(it.sc);
                }
                if(marked_v[x] == 1){
                    interesting_egdes2.push_back(it.sc);
                    marked_v[it.fr] = 1;
                }
                marked2[it.sc] = 1;
                par[it.fr] = x;
                viz[it.fr] = 1;
                Q.push(it.fr);
            }
        }
    }
    int ok = vertex2;
    int l = 0, r = (int)interesting_egdes2.size() - 1;
    reverse(all(interesting_egdes2));
    while(l <= r){
        int last = 0;
        int mid = l + (r - l) / 2;
        vector<int>w(M);
        for(int i=0;i<M;i++){
            if(!marked2[i]) w[i] = 1;
        }
        for(int i=0;i<=mid;i++){
            w[interesting_egdes2[i]] = 1;
        }
        last = interesting_egdes2[mid];
        if(par[U[last]] == V[last]){
            last = U[last];
        }
        else{
            last = V[last];
        }
        long long pls = ask(w);
        if(pls != len_edges * a){
            ok = last;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    vector<int>rs;
    rs.push_back(ok);
    ok = vertex1;
    l = 0, r = (int)interesting_egdes1.size() - 1;
    reverse(all(interesting_egdes1));
    while(l <= r){
        int last = 0;
        int mid = l + (r - l) / 2;
        vector<int>w(M);
        for(int i=0;i<M;i++){
            if(!marked2[i]) w[i] = 1;
        }
        for(int i=0;i<=mid;i++){
            w[interesting_egdes1[i]] = 1;
        }
        last = interesting_egdes1[mid];
        if(par[U[last]] == V[last]){
            last = U[last];
        }
        else{
            last = V[last];
        }
        long long pls = ask(w);
        if(pls != len_edges * a){
            ok = last;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    rs.push_back(ok);
    return rs;
}

void find_pair(int n, vector<int> U, vector<int> V, int A, int B) {
    M = (int)U.size();
    N = n;
    a = A, b = B;
    for(int i=0;i<M;i++){
        nod[U[i]].push_back({V[i], i});
        nod[V[i]].push_back({U[i], i});
    }
    len_edges = find_lenght(A, B);
    int indx = find_index();
    goodedge = indx;
    int vertex1 = U[indx];
    int vertex2 = V[indx];
    vector<int>ans = bfs(vertex1, vertex2, U, V);
    answer(ans[0], ans[1]);
}

Compilation message (stderr)

highway.cpp: In function 'std::vector<int> bfs(int, int, std::vector<int>, std::vector<int>)':
highway.cpp:49:9: warning: unused variable 'marked' [-Wunused-variable]
   49 |     int marked[M], marked2[M];
      |         ^~~~~~

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