Submission #341527

#	Time	Username	Problem	Language	Result	Execution time	Memory
341527		couplefire	Highway Tolls (IOI18_highway)	C++17	100 / 100	502 ms	11180 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;

int n, m;
vector<pair<int, int>> adj[100005];
vector<int> w;
long long dist;
vector<int> vertices[2];

int find(vector<int> arr){
    int lo = 0, hi = arr.size()-1;
    while(lo < hi){
        int mid = lo+(hi-lo+1)/2;
        for(int i = 0; i<m; i++) w[i] = 0;
        for(int i = mid; i<arr.size(); i++) for(auto u : adj[arr[i]]) w[u.second] = 1;
        if(ask(w) != dist) lo = mid;
        else hi = mid-1;
    }
    return arr[lo];
}

void find_pair(int nn, vector<int> uu, vector<int> vv, int aa, int bb){
    n = nn, m = uu.size();
    for(int i = 0; i<m; i++){
        int a = uu[i], b = vv[i];
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    w.assign(m, 0);
    dist = ask(w);
    int lo = 0, hi = m-1;
    while(lo < hi){
        int mid = lo+(hi-lo)/2;
        for(int i = 0; i<m; i++) w[i] = i<=mid;
        if(ask(w) != dist) hi = mid;
        else lo = mid+1;
    }
    vector<int> d(n, n);
    queue<pair<int, int>> q;
    q.push({uu[lo], 0});
    q.push({vv[lo], 1});
    d[uu[lo]] = d[vv[lo]] = 0;
    while(!q.empty()){
        int v = q.front().first; int t = q.front().second;
        vertices[t].push_back(v);
        q.pop();
        for(auto u : adj[v]){
            if(d[u.first]>d[v]+1){
                d[u.first] = d[v]+1;
                q.push({u.first, t});
            }
        }
    }
    // for(auto x : vertices[0]) cout << x << " ";
    // cout << endl;
    // for(auto x : vertices[1]) cout << x << " ";
    // cout << endl;
    answer(find(vertices[0]), find(vertices[1]));
}

Compilation message (stderr)

highway.cpp: In function 'int find(std::vector<int>)':
highway.cpp:16:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(int i = mid; i<arr.size(); i++) for(auto u : adj[arr[i]]) w[u.second] = 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