제출 #222811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
222811		rama_pang	통행료 (IOI18_highway)	C++14	0 / 100	19 ms	1152 KiB

highway

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

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = U.size(), E = -1;
  lint base_cost_light = ask(vector<int>(M, 0));
  
  vector<int> heavy(M, 0);
  vector<int> edge_list[2]; // edges that are in the BFS tree of U[E] and V[E]

  { // Find E
    int lo = 0, hi = M - 1;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      
      for (int i = 0; i <= mid; i++) heavy[i] = 1;
      lint query = ask(heavy);
      for (int i = 0; i <= mid; i++) heavy[i] = 0;

      if (query != base_cost_light) { // one of the heavy edges we set is in the unweighted shortest path
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    E = hi;
  }

  { // Create BFS Tree from both ends of E
    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
      adj[U[i]].emplace_back(i);
      adj[V[i]].emplace_back(i);
    }

    vector<bool> vis(N, false);
    queue<pair<int, int>> q;
    vis[U[E]] = vis[V[E]] = true;
    q.emplace(U[E], 0), q.emplace(V[E], 1);

    while (!q.empty()) {
      int u = q.front().first;
      int t = q.front().second;
      q.pop();
      for (auto e_id : adj[u]) {
        int to = (U[e_id] ^ V[e_id] ^ u);
        if  (vis[to]) continue;
        vis[to] = true;
        q.emplace(to, t);
        edge_list[t].emplace_back(e_id);
        if (V[e_id] == u) swap(U[e_id], V[e_id]); // U is nearer than V
      }
    }
  }
  
  { // Set all edges not in the BFS tree to heavy
    heavy.assign(M, 1);
    for (int t = 0; t < 2; t++) {
      for (auto e : edge_list[t]) {
        heavy[e] = 0;
      }
    }
    heavy[E] = 0;
  }

  auto Get = [&](int root, vector<int> edges) {
    int lo = 0, hi = edges.size();
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      for (int i = 0; i <= mid; i++) heavy[edges[i]] = 1;
      lint query = ask(heavy);
      for (int i = 0; i <= mid; i++) heavy[edges[i]] = 0;
      if (query != base_cost_light) { // heavy edges are used
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    return hi == edges.size() ? root : V[edges[hi]]; // heavy edge in the BFS Tree
  };
  
  return answer(Get(U[E], edge_list[0]), Get(V[E], edge_list[1]));  
}

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

highway.cpp: In lambda function:
highway.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return hi == edges.size() ? root : V[edges[hi]]; // heavy edge in the BFS Tree
            ~~~^~~~~~~~~~~~~~~

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