제출 #222813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
222813		rama_pang	통행료 (IOI18_highway)	C++14	7 / 100	156 ms	8076 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));
  lint base_cost_heavy = (base_cost_light / A) * B;
    
  vector<int> heavy;
  vector<int> edge_list[2]; // edges that are in the BFS tree of U[E] and V[E]

  { // Binary Search to find an edge E which is in the shortest path from S to T if unweighted 
    heavy.assign(M, 0);
    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
      }
    }
  }
  
  auto Get = [&](int root, vector<int> edges) { // Binary Search to find S and T
    heavy.assign(M, 1);
    int lo = 0, hi = edges.size();

    while (lo < hi) {
      int mid = (lo + hi) / 2;

      for (int i = mid + 1; i < edges.size(); i++) heavy[edges[i]] = 0;
      lint query = ask(heavy);
      for (int i = mid + 1; i < edges.size(); i++) heavy[edges[i]] = 1;
      
      if (query == base_cost_heavy) { // all edges in the BFS tree from S to root is heavy
        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:69:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = mid + 1; i < edges.size(); i++) heavy[edges[i]] = 0;
                             ~~^~~~~~~~~~~~~~
highway.cpp:71:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = mid + 1; i < edges.size(); i++) heavy[edges[i]] = 1;
                             ~~^~~~~~~~~~~~~~
highway.cpp:80: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: 7 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31