Submission #289370

#	Time	Username	Problem	Language	Result	Execution time	Memory
289370		dolphingarlic	Highway Tolls (IOI18_highway)	C++14	0 / 100	135 ms	8852 KiB

highway

#include "highway.h"

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

vector<pair<int, int>> graph[90000], ord[2];
bool visited[90000];
int ans[2];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    for (int i = 0; i < N; i++) {
        graph[i].clear();
        visited[i] = false;
    }
    ord[0].clear(); ord[1].clear();

    int M = int(U.size());
    for (int i = 0; i < M; i++) {
        graph[U[i]].push_back({V[i], i});
        graph[V[i]].push_back({U[i], i});
    }

    vector<int> W(M, 0);
    long long path_len = ask(W) / A;

    int l = 0, r = M - 1;
    while (l != r) {
        int mid = (l + r) / 2;
        fill(W.begin(), W.end(), 0);
        for (int i = 0; i <= mid; i++) W[i] = 1;
        long long res = ask(W);
        if (res == path_len) l = mid + 1;
        else r = mid;
    }
    int m_edge = l, uu = U[l], vv = V[l];

    visited[uu] = visited[vv] = true;
    queue<pair<int, int>> q;
    q.push({uu, 0}); q.push({vv, 1});
    ord[0].push_back({uu, -1}); ord[1].push_back({vv, -1});
    while (q.size()) {
        int curr, sub;
        tie(curr, sub) = q.front();
        q.pop();
        for (pair<int, int> i : graph[curr]) {
            if (!visited[i.first] && i.second > m_edge) {
                visited[i.first] = true;
                ord[sub].push_back(i);
                q.push({i.first, sub});
            }
        }
    }

    for (int s = 0; s < 2; s++) {
        l = 0, r = ord[s].size() - 1;
        while (l != r) {
            int mid = (l + r) / 2;

            fill(W.begin(), W.end(), 1);
            for (int i = mid + 1; i < ord[s].size(); i++) W[ord[s][i].second] = 0;

            long long dist = ask(W);
            if (dist == path_len * B) r = mid;
            else l = mid + 1;
        }
        ans[s] = ord[s][l].first;
    }

    answer(ans[0], ans[1]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:60:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             for (int i = mid + 1; i < ord[s].size(); i++) W[ord[s][i].second] = 0;
      |                                   ~~^~~~~~~~~~~~~~~

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