Submission #222816

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
222816	2020-04-14 03:57:18	rama_pang	Highway Tolls (IOI18_highway)	C++14	100 / 100	222 ms	9292 KiB

highway

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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 < M; i++) heavy[i] = i <= mid;
      if (ask(heavy) != base_cost_light) { // one of the heavy edges we set is in the unweighted shortest path
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    E = hi;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:10:8: warning: unused variable 'base_cost_heavy' [-Wunused-variable]
   lint base_cost_heavy = (base_cost_light / A) * B;
        ^~~~~~~~~~~~~~~

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