oj.uz

Submission #284634

# Submission time Handle Problem Language Result Execution time Memory
284634 2020-08-27T18:58:16 Z azret Highway Tolls (IOI18_highway) C++14
90 / 100
 274 ms 10972 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;
        } else if (d[i.second] == d[w]) {
          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 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 288 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 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 392 KB Output is correct
2 Correct 14 ms 1280 KB Output is correct
3 Correct 170 ms 8740 KB Output is correct
4 Correct 161 ms 8740 KB Output is correct
5 Correct 162 ms 8740 KB Output is correct
6 Correct 161 ms 8816 KB Output is correct
7 Correct 179 ms 8792 KB Output is correct
8 Correct 164 ms 8752 KB Output is correct
9 Correct 160 ms 8748 KB Output is correct
10 Correct 158 ms 8904 KB Output is correct
11 Correct 172 ms 8280 KB Output is correct
12 Correct 157 ms 8336 KB Output is correct
13 Correct 180 ms 8216 KB Output is correct
14 Correct 163 ms 8156 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1152 KB Output is correct
2 Correct 27 ms 2128 KB Output is correct
3 Correct 40 ms 2964 KB Output is correct
4 Correct 120 ms 8212 KB Output is correct
5 Correct 121 ms 8144 KB Output is correct
6 Correct 125 ms 8188 KB Output is correct
7 Correct 123 ms 8148 KB Output is correct
8 Correct 124 ms 8168 KB Output is correct
9 Correct 122 ms 8268 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 16 ms 1272 KB Output is correct
3 Correct 116 ms 6916 KB Output is correct
4 Correct 159 ms 8732 KB Output is correct
5 Correct 150 ms 8732 KB Output is correct
6 Correct 144 ms 8816 KB Output is correct
7 Correct 155 ms 8824 KB Output is correct
8 Correct 158 ms 8840 KB Output is correct
9 Correct 154 ms 8736 KB Output is correct
10 Correct 178 ms 8800 KB Output is correct
11 Correct 194 ms 8152 KB Output is correct
12 Correct 168 ms 8152 KB Output is correct
13 Correct 220 ms 8192 KB Output is correct
14 Correct 193 ms 8216 KB Output is correct
15 Correct 201 ms 8956 KB Output is correct
16 Correct 194 ms 8924 KB Output is correct
17 Correct 211 ms 8184 KB Output is correct
18 Correct 164 ms 8160 KB Output is correct
19 Correct 198 ms 8760 KB Output is correct
20 Correct 150 ms 8152 KB Output is correct
21 Correct 170 ms 9220 KB Output is correct
22 Correct 121 ms 9224 KB Output is correct
23 Correct 189 ms 9100 KB Output is correct
24 Correct 185 ms 9016 KB Output is correct
25 Correct 210 ms 8252 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1280 KB Output is correct
2 Correct 18 ms 1348 KB Output is correct
3 Correct 181 ms 9276 KB Output is correct
4 Correct 197 ms 9852 KB Output is correct
5 Correct 274 ms 10868 KB Output is correct
6 Correct 231 ms 10860 KB Output is correct
7 Correct 231 ms 10856 KB Output is correct
8 Correct 250 ms 10960 KB Output is correct
9 Correct 181 ms 7824 KB Output is correct
10 Correct 177 ms 8152 KB Output is correct
11 Correct 188 ms 8716 KB Output is correct
12 Correct 230 ms 10260 KB Output is correct
13 Correct 250 ms 10500 KB Output is correct
14 Correct 247 ms 10908 KB Output is correct
15 Correct 247 ms 10840 KB Output is correct
16 Correct 218 ms 8992 KB Output is correct
17 Correct 154 ms 9280 KB Output is correct
18 Correct 150 ms 9528 KB Output is correct
19 Correct 147 ms 9364 KB Output is correct
20 Correct 159 ms 9440 KB Output is correct
21 Correct 231 ms 10828 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1280 KB Output is correct
2 Correct 20 ms 1280 KB Output is correct
3 Partially correct 180 ms 9260 KB Output is partially correct
4 Correct 186 ms 9468 KB Output is correct
5 Correct 213 ms 9776 KB Output is correct
6 Partially correct 230 ms 10972 KB Output is partially correct
7 Partially correct 189 ms 9244 KB Output is partially correct
8 Partially correct 174 ms 9460 KB Output is partially correct
9 Partially correct 200 ms 9804 KB Output is partially correct
10 Partially correct 228 ms 10848 KB Output is partially correct
11 Partially correct 222 ms 10852 KB Output is partially correct
12 Partially correct 224 ms 10932 KB Output is partially correct
13 Correct 183 ms 8728 KB Output is correct
14 Correct 191 ms 8164 KB Output is correct
15 Correct 184 ms 8708 KB Output is correct
16 Correct 187 ms 8160 KB Output is correct
17 Correct 183 ms 8748 KB Output is correct
18 Correct 174 ms 8224 KB Output is correct
19 Correct 214 ms 10180 KB Output is correct
20 Correct 205 ms 10584 KB Output is correct
21 Partially correct 230 ms 10852 KB Output is partially correct
22 Partially correct 236 ms 10892 KB Output is partially correct
23 Partially correct 233 ms 10844 KB Output is partially correct
24 Partially correct 238 ms 10968 KB Output is partially correct
25 Partially correct 226 ms 10960 KB Output is partially correct
26 Correct 232 ms 10860 KB Output is correct
27 Partially correct 161 ms 9528 KB Output is partially correct
28 Partially correct 156 ms 9372 KB Output is partially correct
29 Partially correct 141 ms 9680 KB Output is partially correct
30 Partially correct 144 ms 9556 KB Output is partially correct
31 Correct 159 ms 9504 KB Output is correct
32 Correct 156 ms 9308 KB Output is correct
33 Correct 137 ms 9636 KB Output is correct
34 Correct 148 ms 9352 KB Output is correct
35 Partially correct 144 ms 9368 KB Output is partially correct
36 Correct 140 ms 9368 KB Output is correct
37 Partially correct 144 ms 9592 KB Output is partially correct
38 Partially correct 157 ms 9468 KB Output is partially correct
39 Partially correct 229 ms 10856 KB Output is partially correct
40 Partially correct 229 ms 10888 KB Output is partially correct
41 Partially correct 241 ms 10904 KB Output is partially correct
42 Partially correct 224 ms 10820 KB Output is partially correct