oj.uz

Submission #422042

# Submission time Handle Problem Language Result Execution time Memory
422042 2021-06-09T15:44:56 Z Sundavar Highway Tolls (IOI18_highway) C++14
100 / 100
 322 ms 12700 KB 
#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)
      if(graph[a.first].start == -1){
        q.push_back(a.first);
        graph[a.first].start = graph[curr].start;
        graph[a.first].depth = graph[curr].depth + 1;
        graph[a.first].with = a.second;
      }
  }
}
bool sortFunc(int a, int b){
  return graph[a].depth < graph[b].depth;
}
int find(int u, int N, int M, ll length, ll A, ll B){
  vector<int> S(M, 1);
  vector<int> poss;
  for(int i = 0; i < N; i++)
    if(graph[i].start == u) poss.push_back(i);
  sort(poss.begin(), poss.end(), sortFunc);
  int l = 0, r = poss.size();
  while(r-l > 1){
    int m = (l+r)/2-1;
    S.assign(M, 1);
    for(int i = 0; i < N; i++)
      if(graph[i].start != u) S[graph[i].with] = 0;
    for(int i = 0; i <= m; i++) S[graph[poss[i]].with] = 0;
    if(ask(S) == length*A)
      r = m+1;
    else
      l = m+1;
  }
  return poss[l];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
  graph.resize(N);
  int M = U.size();
  for(int i = 0; i < M; i++){
    graph[U[i]].to.push_back({V[i],i});
    graph[V[i]].to.push_back({U[i],i});
  }
  vector<int> S(M, 0);
  ll dist = ask(S), length = dist/A;
  s.resize(M, 0);
  int ind = getEdge(0, M, M, dist);
  BFS(V[ind], U[ind], ind);
  answer(find(U[ind], N, M, length, A, B), find(V[ind], N, M, length, A, B));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 200 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 16 ms 1452 KB Output is correct
3 Correct 228 ms 10604 KB Output is correct
4 Correct 189 ms 10324 KB Output is correct
5 Correct 225 ms 10340 KB Output is correct
6 Correct 211 ms 10324 KB Output is correct
7 Correct 209 ms 10328 KB Output is correct
8 Correct 142 ms 10336 KB Output is correct
9 Correct 147 ms 10560 KB Output is correct
10 Correct 168 ms 10436 KB Output is correct
11 Correct 193 ms 9584 KB Output is correct
12 Correct 240 ms 9888 KB Output is correct
13 Correct 220 ms 9648 KB Output is correct
14 Correct 172 ms 9944 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1256 KB Output is correct
2 Correct 33 ms 2368 KB Output is correct
3 Correct 59 ms 3452 KB Output is correct
4 Correct 136 ms 9492 KB Output is correct
5 Correct 159 ms 9488 KB Output is correct
6 Correct 120 ms 9664 KB Output is correct
7 Correct 165 ms 10044 KB Output is correct
8 Correct 127 ms 9480 KB Output is correct
9 Correct 176 ms 9880 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 21 ms 1392 KB Output is correct
3 Correct 125 ms 8236 KB Output is correct
4 Correct 189 ms 10200 KB Output is correct
5 Correct 159 ms 10580 KB Output is correct
6 Correct 163 ms 10252 KB Output is correct
7 Correct 144 ms 10592 KB Output is correct
8 Correct 168 ms 10532 KB Output is correct
9 Correct 167 ms 10700 KB Output is correct
10 Correct 226 ms 10544 KB Output is correct
11 Correct 193 ms 9964 KB Output is correct
12 Correct 241 ms 9672 KB Output is correct
13 Correct 229 ms 9900 KB Output is correct
14 Correct 200 ms 9588 KB Output is correct
15 Correct 138 ms 10232 KB Output is correct
16 Correct 183 ms 10280 KB Output is correct
17 Correct 190 ms 9940 KB Output is correct
18 Correct 202 ms 9968 KB Output is correct
19 Correct 193 ms 10556 KB Output is correct
20 Correct 184 ms 9644 KB Output is correct
21 Correct 166 ms 10688 KB Output is correct
22 Correct 153 ms 10676 KB Output is correct
23 Correct 157 ms 10308 KB Output is correct
24 Correct 159 ms 10328 KB Output is correct
25 Correct 229 ms 10036 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1472 KB Output is correct
2 Correct 20 ms 1524 KB Output is correct
3 Correct 180 ms 10732 KB Output is correct
4 Correct 270 ms 11308 KB Output is correct
5 Correct 275 ms 12284 KB Output is correct
6 Correct 282 ms 12320 KB Output is correct
7 Correct 218 ms 12304 KB Output is correct
8 Correct 296 ms 12212 KB Output is correct
9 Correct 209 ms 8288 KB Output is correct
10 Correct 194 ms 8516 KB Output is correct
11 Correct 214 ms 9484 KB Output is correct
12 Correct 207 ms 11120 KB Output is correct
13 Correct 270 ms 11636 KB Output is correct
14 Correct 316 ms 12144 KB Output is correct
15 Correct 264 ms 12280 KB Output is correct
16 Correct 234 ms 9464 KB Output is correct
17 Correct 177 ms 10792 KB Output is correct
18 Correct 172 ms 10704 KB Output is correct
19 Correct 136 ms 10864 KB Output is correct
20 Correct 148 ms 10696 KB Output is correct
21 Correct 253 ms 12320 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1344 KB Output is correct
2 Correct 24 ms 1472 KB Output is correct
3 Correct 185 ms 10560 KB Output is correct
4 Correct 250 ms 10960 KB Output is correct
5 Correct 226 ms 11220 KB Output is correct
6 Correct 306 ms 12156 KB Output is correct
7 Correct 148 ms 10728 KB Output is correct
8 Correct 182 ms 10952 KB Output is correct
9 Correct 248 ms 11032 KB Output is correct
10 Correct 246 ms 12284 KB Output is correct
11 Correct 234 ms 12212 KB Output is correct
12 Correct 229 ms 12236 KB Output is correct
13 Correct 217 ms 9372 KB Output is correct
14 Correct 177 ms 8648 KB Output is correct
15 Correct 149 ms 9392 KB Output is correct
16 Correct 151 ms 8512 KB Output is correct
17 Correct 206 ms 9372 KB Output is correct
18 Correct 223 ms 8572 KB Output is correct
19 Correct 282 ms 11120 KB Output is correct
20 Correct 222 ms 11756 KB Output is correct
21 Correct 259 ms 12172 KB Output is correct
22 Correct 234 ms 12092 KB Output is correct
23 Correct 304 ms 12180 KB Output is correct
24 Correct 322 ms 12100 KB Output is correct
25 Correct 265 ms 12328 KB Output is correct
26 Correct 282 ms 12244 KB Output is correct
27 Correct 195 ms 10884 KB Output is correct
28 Correct 193 ms 10544 KB Output is correct
29 Correct 160 ms 11056 KB Output is correct
30 Correct 197 ms 10976 KB Output is correct
31 Correct 141 ms 10884 KB Output is correct
32 Correct 144 ms 10952 KB Output is correct
33 Correct 200 ms 10800 KB Output is correct
34 Correct 141 ms 10864 KB Output is correct
35 Correct 155 ms 10868 KB Output is correct
36 Correct 196 ms 10464 KB Output is correct
37 Correct 137 ms 10960 KB Output is correct
38 Correct 220 ms 10680 KB Output is correct
39 Correct 293 ms 12532 KB Output is correct
40 Correct 273 ms 12700 KB Output is correct
41 Correct 259 ms 12400 KB Output is correct
42 Correct 311 ms 12280 KB Output is correct