Submission #806642

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
806642	2023-08-04 08:28:14	Trisanu_Das	Highway Tolls (IOI18_highway)	C++17	100 / 100	209 ms	11228 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 <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define ll long long
 
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = size(U), x = 0, u, d[2][N];
  ll least = ask(vector<int> (M));
  for(int b = 1<<17; b/=2; ) if(x + b < M) {
    vector<int> w(M);
    fill(begin(w), begin(w) + x + b, 1);
    if(ask(w) == least) x |= b;
  }
 
  array<int, 2> S = {U[x], V[x]}, ans {};
  vector<array<int, 2>> g[N], a;
  for(int i = x; i < M; i++) {
    g[U[i]].push_back({V[i], i});
    g[V[i]].push_back({U[i], i});
  }
  for(int k : {0, 1}) {
    fill(d[k], d[k] + N, N);
    queue<int> q;
    d[k][S[k]] = 0;
    q.push(S[k]);
    while(!empty(q)) {
      u = q.front(); q.pop();
      for(auto &[v, e] : g[u]) if(d[k][v] > d[k][u] + 1) d[k][v] = d[k][u] + 1, q.push(v);
    }
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:35:44: warning: comparison of integer expressions of different signedness: 'std::array<int, 2>::value_type' {aka 'int'} and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int b = 1<<17; b/=2; ) if(ans[k] + b < size(a)) {

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