Submission #422042

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
422042	2021-06-09 15:44:56	Sundavar	Highway Tolls (IOI18_highway)	C++14	100 / 100	322 ms	12700 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;
typedef pair<int,int> pii;
typedef long long ll;
struct node{
  vector<pii> to;
  int depth = 0, start = -1, with = -1;
};
vector<node> graph;
vector<int> s;
int getEdge(int l, int r, int M, ll dist){
  if(l+1 == r) return l;
  int m = (l+r)/2-1;
  s.assign(M, 0);
  for(int i = 0; i <= m; i++) s[i] = 1;
  if(ask(s) == dist)
    return getEdge(m+1, r, M, dist);
  else
    return getEdge(l, m+1, M, dist);
}
void BFS(int x, int y, int id){
  deque<int> q;
  q.push_back(x), q.push_back(y);
  graph[x].start = x, graph[y].start = y;
  graph[x].with = graph[y].with = id;
  while(q.size() > 0){
    int curr = q.front();
    q.pop_front();
    for(pii& a : graph[curr].to)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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