제출 #597027

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
597027		SlavicG	통행료 (IOI18_highway)	C++17	100 / 100	255 ms	19992 KiB

highway

#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 4e5 + 10;
vector<pair<int, int>> adj[N];

long long start;
int query(int s, int m, vector<pair<int, int>> edges, vector<int> paiu) {
    if(edges.empty()) return s;
    int l = 0, r = (int)edges.size() - 1;
    vector<int> c(m, 0);
    for(auto x: paiu) c[x] = 1;
    reverse(edges.begin(), edges.end());
    int pos = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        vector<int> rem = c;
        for(int j = 0; j <= mid; ++j) {
            c[edges[j].first] = 1;
        }
        if(ask(c) > start) {
            pos = mid, r = mid - 1;
        } else l = mid + 1;
        c = rem;
    }
    if(pos == -1) return s;
    return edges[pos].second;
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
    int m = u.size();
    start = ask(vector<int>(m, 0));
    for(int i = 0; i < m; ++i) {
        adj[u[i]].push_back({i, v[i]});
        adj[v[i]].push_back({i, u[i]});
    }
    int l = 0, r = m - 1, p = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        vector<int> qr(m, 0);
        for(int j = 0; j <= mid; ++j) qr[j] = 1;
        if(ask(qr) > start) {
            p = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    assert(p != -1);
    vector<vector<int>> dist(2, vector<int>(n, -1));
    vector<int> nodes = {u[p], v[p]};

    for(int j = 0; j < 2; ++j) {
        queue<int> q; q.push(nodes[j]);
        dist[j][nodes[j]] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(auto x: adj[u]) {
                int v = x.second;
                if(dist[j][v] == -1) {
                    dist[j][v] = dist[j][u] + 1;
                    q.push(v);
                }
            }
        }
    }
    vector<int> ans(2);
    for(int j = 0; j < 2; ++j) {
        vector<pair<int, int>> edges;
        queue<int> q; q.push(nodes[j]);
        vector<int> d(n, -1), paiu;
        d[nodes[j]] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(auto x: adj[u]) {
                int idx = x.first, v = x.second;
                if(dist[j][v] < dist[j ^ 1][v]) {
                    if(d[v] == -1) {
                        d[v] = d[u] + 1;
                        q.push(v);
                        edges.push_back({idx, v});
                    } else if(d[v] == d[u] + 1) {
                        paiu.push_back(idx);
                    }
                } else if(idx != p) {
                    paiu.push_back(idx);
                }
            }
        }
        ans[j] = query(nodes[j], m, edges, paiu);
    }
    //assert(ans[0] == 0 || ans[1] == 0);
    answer(ans[0], ans[1]);
}

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'int query(int, int, std::vector<std::pair<int, int> >, std::vector<int>)':
highway.cpp:16:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |         int mid = l + r >> 1;
      |                   ~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:39:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid = l + r >> 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