oj.uz

Submission #284630

# Submission time Handle Problem Language Result Execution time Memory
284630 2020-08-27T18:50:58 Z azret Highway Tolls (IOI18_highway) C++14
90 / 100
 314 ms 11008 KB 
// Task: Highway Tolls (IOI 2018)
// Solves subtask 6 for partial points
// Author: Tomasz Idziaszek


#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)


vector<int> w;
long long W;
int M;
vector<vector<pair<int,int> > > adj;
vector<int> edge, vert;
int E;


int get_first_edge() {
  int lb = 0, ub = M-1;
  while (lb != ub) {
    int mid = (lb + ub) / 2;
    REP(i, M) {
      w[i] = i <= mid;
    }
    if (ask(w) != W) {
      ub = mid;
    } else {
      lb = mid+1;
    }
  }
  return lb;
}

int get_last_edge() {
  int lb = -1, ub = E-1;
  while (lb != ub) {
    int mid = (lb + ub + 1) / 2;
    REP(i, M) {
      w[i] = edge[i] >= mid;
    }
    if (ask(w) != W) {
      lb = mid;
    } else {
      ub = mid-1;
    }
  }
  return lb;
}


void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  M = U.size();
  w.resize(M);
  W = ask(w);

  adj.resize(N);
  REP(i, M) {
    adj[U[i]].push_back(make_pair(i, V[i]));
    adj[V[i]].push_back(make_pair(i, U[i]));
  }

  edge.resize(M);
  vert.resize(M);

  int e = get_first_edge();
  int v = U[e];
  int ans[2];

  REP(j, 2) {
    E = 0;
    queue<int> q;
    vector<int> d(N, -1);
    d[v] = 0;
    q.push(v);

    while (!q.empty()) {
      int w = q.front();
      q.pop();

      for (auto& i : adj[w]) {
        if (d[i.second] == -1) {
          d[i.second] = d[w] + 1;
          vert[E] = i.second;
          edge[i.first] = E++;
          q.push(i.second);
        } else if (d[i.second] == d[w] + 1) {
          edge[i.first] = N;
        }
      }
    }

    int el = get_last_edge();
    v = ans[j] = vert[el];
  }

  answer(ans[0], ans[1]);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 14 ms 1272 KB Output is correct
3 Correct 212 ms 8752 KB Output is correct
4 Correct 202 ms 8768 KB Output is correct
5 Correct 169 ms 8740 KB Output is correct
6 Correct 158 ms 8736 KB Output is correct
7 Correct 158 ms 8764 KB Output is correct
8 Correct 158 ms 8756 KB Output is correct
9 Correct 205 ms 8760 KB Output is correct
10 Correct 214 ms 8740 KB Output is correct
11 Correct 156 ms 8284 KB Output is correct
12 Correct 230 ms 8176 KB Output is correct
13 Correct 162 ms 8156 KB Output is correct
14 Correct 206 ms 8152 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1212 KB Output is correct
2 Correct 26 ms 2040 KB Output is correct
3 Correct 43 ms 2988 KB Output is correct
4 Correct 123 ms 8136 KB Output is correct
5 Correct 133 ms 8156 KB Output is correct
6 Correct 145 ms 8136 KB Output is correct
7 Correct 122 ms 8148 KB Output is correct
8 Correct 110 ms 8144 KB Output is correct
9 Correct 175 ms 8156 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 17 ms 1280 KB Output is correct
3 Correct 155 ms 6912 KB Output is correct
4 Correct 153 ms 8736 KB Output is correct
5 Correct 155 ms 8744 KB Output is correct
6 Correct 183 ms 8740 KB Output is correct
7 Correct 159 ms 8768 KB Output is correct
8 Correct 199 ms 8828 KB Output is correct
9 Correct 215 ms 8748 KB Output is correct
10 Correct 210 ms 8764 KB Output is correct
11 Correct 162 ms 8184 KB Output is correct
12 Correct 160 ms 8152 KB Output is correct
13 Correct 182 ms 8144 KB Output is correct
14 Correct 160 ms 8152 KB Output is correct
15 Correct 197 ms 8748 KB Output is correct
16 Correct 202 ms 8852 KB Output is correct
17 Correct 164 ms 8148 KB Output is correct
18 Correct 175 ms 8156 KB Output is correct
19 Correct 189 ms 8784 KB Output is correct
20 Correct 172 ms 8164 KB Output is correct
21 Correct 140 ms 9268 KB Output is correct
22 Correct 136 ms 9216 KB Output is correct
23 Correct 132 ms 9024 KB Output is correct
24 Correct 189 ms 8956 KB Output is correct
25 Correct 228 ms 8284 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1280 KB Output is correct
2 Correct 23 ms 1400 KB Output is correct
3 Correct 195 ms 9212 KB Output is correct
4 Correct 206 ms 9744 KB Output is correct
5 Correct 314 ms 10868 KB Output is correct
6 Correct 241 ms 10864 KB Output is correct
7 Correct 270 ms 10852 KB Output is correct
8 Correct 299 ms 10948 KB Output is correct
9 Correct 208 ms 7832 KB Output is correct
10 Correct 262 ms 8168 KB Output is correct
11 Correct 264 ms 8720 KB Output is correct
12 Correct 258 ms 10100 KB Output is correct
13 Correct 292 ms 10500 KB Output is correct
14 Correct 305 ms 10964 KB Output is correct
15 Correct 274 ms 11008 KB Output is correct
16 Correct 207 ms 8912 KB Output is correct
17 Correct 192 ms 9276 KB Output is correct
18 Correct 200 ms 9548 KB Output is correct
19 Correct 139 ms 9368 KB Output is correct
20 Correct 145 ms 9440 KB Output is correct
21 Correct 246 ms 10824 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1272 KB Output is correct
2 Correct 17 ms 1364 KB Output is correct
3 Partially correct 216 ms 9248 KB Output is partially correct
4 Correct 208 ms 9512 KB Output is correct
5 Correct 239 ms 9748 KB Output is correct
6 Partially correct 250 ms 10840 KB Output is partially correct
7 Partially correct 225 ms 9252 KB Output is partially correct
8 Partially correct 173 ms 9452 KB Output is partially correct
9 Partially correct 272 ms 9748 KB Output is partially correct
10 Partially correct 234 ms 10852 KB Output is partially correct
11 Partially correct 241 ms 10888 KB Output is partially correct
12 Partially correct 242 ms 10860 KB Output is partially correct
13 Correct 191 ms 8756 KB Output is correct
14 Correct 206 ms 8152 KB Output is correct
15 Correct 178 ms 8788 KB Output is correct
16 Correct 177 ms 8344 KB Output is correct
17 Correct 196 ms 8740 KB Output is correct
18 Correct 169 ms 8228 KB Output is correct
19 Correct 220 ms 10128 KB Output is correct
20 Correct 209 ms 10512 KB Output is correct
21 Partially correct 232 ms 10844 KB Output is partially correct
22 Partially correct 234 ms 10836 KB Output is partially correct
23 Partially correct 221 ms 10840 KB Output is partially correct
24 Partially correct 259 ms 10844 KB Output is partially correct
25 Partially correct 295 ms 10856 KB Output is partially correct
26 Correct 250 ms 10848 KB Output is correct
27 Partially correct 142 ms 9560 KB Output is partially correct
28 Partially correct 150 ms 9344 KB Output is partially correct
29 Partially correct 154 ms 9768 KB Output is partially correct
30 Partially correct 146 ms 9480 KB Output is partially correct
31 Correct 148 ms 9420 KB Output is correct
32 Correct 138 ms 9288 KB Output is correct
33 Correct 150 ms 9692 KB Output is correct
34 Correct 144 ms 9356 KB Output is correct
35 Partially correct 143 ms 9364 KB Output is partially correct
36 Correct 136 ms 9332 KB Output is correct
37 Partially correct 143 ms 9628 KB Output is partially correct
38 Partially correct 154 ms 9536 KB Output is partially correct
39 Partially correct 231 ms 10840 KB Output is partially correct
40 Partially correct 239 ms 10836 KB Output is partially correct
41 Partially correct 239 ms 10836 KB Output is partially correct
42 Partially correct 243 ms 10912 KB Output is partially correct