oj.uz

Submission #596893

# Submission time Handle Problem Language Result Execution time Memory
596893 2022-07-15T08:51:24 Z Sam_a17 Highway Tolls (IOI18_highway) C++14
100 / 100
 270 ms 19544 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

long long ask(const std::vector<int> &w);
void answer(int s, int t);

const int maxN = 2e5 + 10;
vector<pair<int, int>> adj[maxN], g[maxN];
int n, m, u[maxN], v[maxN];
long long a, b;

template<typename F>
void pr(F a) {
  cerr << a << endl;
}

template<typename T>
void pr(vector<T>& a) {
  cerr << "[ ";
  for(auto i: a) {
    cerr << i << " ";
  }
  cerr << "]" << endl;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N, m = sz(U), a = A, b = B;
  vector<int> to_ask(m, 0);
  long long start = ask(to_ask);
  bool flag = true;

	for(int i = 0; i < m; i++) {
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});

    u[i] = U[i], v[i] = V[i];
	}

  int ina = 0, inb = m - 1, res = -1;
  while(ina <= inb) {
    int mid = (ina + inb) / 2;
    vector<int> toask(m, 0);
    for(int i = 0; i <= mid; i++) {
      toask[i] = 1;
    }
    long long ansi = ask(toask);

    if(ansi != start) {
      res = mid;
      inb = mid - 1;
    } else {
      ina = mid + 1;
    }
  }

  // we get edge
  // u[res]: v[res]

  vector<int> left, right;
  vector<bool> vis(n);
  queue<pair<int, int>> q;
  
  q.push({u[res], 1});
  q.push({v[res], 2});

  left.push_back(u[res]);
  right.push_back(v[res]);

  vis[u[res]] = vis[v[res]] = true;

  while(!q.empty()) {
    auto u = q.front();
    q.pop();

    for(auto i: adj[u.first]) {
      if(vis[i.first]) continue;
      vis[i.first] = true;
      if(u.second == 1) {
        left.push_back(i.first);
      } else {
        right.push_back(i.first);
      }
      q.push({i.first, u.second});
    }
  }

  // pr(left);
  // pr(right);

  auto solve = [&](vector<int>& nodes)->int {
    int ina = 0, inb = sz(nodes) - 1, res = -1;
    while(ina <= inb) {
      int mid = (ina + inb) / 2;
      vector<int> toask(m, 1), del(n);
      for(int i = mid + 1; i < sz(nodes); i++) {
        del[nodes[i]] = 1;
      }

      for(int i = 0; i < m; i++) {
        if(!del[u[i]] && !del[v[i]]) {
          toask[i] = 0;
        }
      }

      long long ansi = ask(toask);

      if(ansi == start) {
        res = mid;
        inb = mid - 1;
      } else {
        ina = mid + 1;
      }
    }
    // pr(res);
    assert(res != -1);
    return nodes[res];
  };

  answer(solve(left), solve(right));
}

Compilation message

highway.cpp: In lambda function:
highway.cpp:101:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |       for(int i = mid + 1; i < sz(nodes); i++) {
      |                              ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:36:8: warning: unused variable 'flag' [-Wunused-variable]
   36 |   bool flag = true;
      |        ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 19 ms 10488 KB Output is correct
3 Correct 125 ms 16732 KB Output is correct
4 Correct 125 ms 16708 KB Output is correct
5 Correct 124 ms 16824 KB Output is correct
6 Correct 154 ms 16736 KB Output is correct
7 Correct 152 ms 16828 KB Output is correct
8 Correct 158 ms 16724 KB Output is correct
9 Correct 107 ms 16736 KB Output is correct
10 Correct 165 ms 16708 KB Output is correct
11 Correct 140 ms 16428 KB Output is correct
12 Correct 150 ms 16124 KB Output is correct
13 Correct 169 ms 16196 KB Output is correct
14 Correct 160 ms 16252 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10320 KB Output is correct
2 Correct 23 ms 11164 KB Output is correct
3 Correct 38 ms 11944 KB Output is correct
4 Correct 115 ms 16420 KB Output is correct
5 Correct 94 ms 16556 KB Output is correct
6 Correct 138 ms 16364 KB Output is correct
7 Correct 137 ms 16152 KB Output is correct
8 Correct 99 ms 16300 KB Output is correct
9 Correct 99 ms 16192 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9680 KB Output is correct
2 Correct 19 ms 10528 KB Output is correct
3 Correct 91 ms 15332 KB Output is correct
4 Correct 142 ms 16744 KB Output is correct
5 Correct 146 ms 16692 KB Output is correct
6 Correct 125 ms 16684 KB Output is correct
7 Correct 88 ms 16744 KB Output is correct
8 Correct 148 ms 16724 KB Output is correct
9 Correct 151 ms 16824 KB Output is correct
10 Correct 133 ms 16816 KB Output is correct
11 Correct 130 ms 16080 KB Output is correct
12 Correct 140 ms 16188 KB Output is correct
13 Correct 155 ms 16344 KB Output is correct
14 Correct 144 ms 16300 KB Output is correct
15 Correct 114 ms 16760 KB Output is correct
16 Correct 122 ms 16720 KB Output is correct
17 Correct 151 ms 16140 KB Output is correct
18 Correct 133 ms 16116 KB Output is correct
19 Correct 130 ms 16708 KB Output is correct
20 Correct 167 ms 16136 KB Output is correct
21 Correct 158 ms 17228 KB Output is correct
22 Correct 106 ms 17220 KB Output is correct
23 Correct 121 ms 17176 KB Output is correct
24 Correct 121 ms 17128 KB Output is correct
25 Correct 134 ms 16280 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10576 KB Output is correct
2 Correct 19 ms 10488 KB Output is correct
3 Correct 139 ms 17264 KB Output is correct
4 Correct 261 ms 17860 KB Output is correct
5 Correct 238 ms 19124 KB Output is correct
6 Correct 270 ms 19240 KB Output is correct
7 Correct 232 ms 19364 KB Output is correct
8 Correct 206 ms 19352 KB Output is correct
9 Correct 188 ms 17048 KB Output is correct
10 Correct 145 ms 17508 KB Output is correct
11 Correct 140 ms 17760 KB Output is correct
12 Correct 184 ms 18948 KB Output is correct
13 Correct 243 ms 19184 KB Output is correct
14 Correct 240 ms 19356 KB Output is correct
15 Correct 206 ms 19056 KB Output is correct
16 Correct 186 ms 18136 KB Output is correct
17 Correct 137 ms 17228 KB Output is correct
18 Correct 134 ms 17424 KB Output is correct
19 Correct 109 ms 17336 KB Output is correct
20 Correct 130 ms 17444 KB Output is correct
21 Correct 181 ms 18920 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10448 KB Output is correct
2 Correct 17 ms 10576 KB Output is correct
3 Correct 151 ms 17304 KB Output is correct
4 Correct 194 ms 17892 KB Output is correct
5 Correct 169 ms 18020 KB Output is correct
6 Correct 201 ms 19204 KB Output is correct
7 Correct 133 ms 17180 KB Output is correct
8 Correct 150 ms 17748 KB Output is correct
9 Correct 221 ms 18168 KB Output is correct
10 Correct 222 ms 19476 KB Output is correct
11 Correct 202 ms 19364 KB Output is correct
12 Correct 248 ms 19272 KB Output is correct
13 Correct 157 ms 17864 KB Output is correct
14 Correct 161 ms 17520 KB Output is correct
15 Correct 133 ms 17948 KB Output is correct
16 Correct 143 ms 17520 KB Output is correct
17 Correct 220 ms 17840 KB Output is correct
18 Correct 175 ms 17584 KB Output is correct
19 Correct 190 ms 18992 KB Output is correct
20 Correct 166 ms 18920 KB Output is correct
21 Correct 255 ms 19480 KB Output is correct
22 Correct 202 ms 19352 KB Output is correct
23 Correct 209 ms 19372 KB Output is correct
24 Correct 231 ms 19360 KB Output is correct
25 Correct 236 ms 19184 KB Output is correct
26 Correct 187 ms 19544 KB Output is correct
27 Correct 121 ms 17380 KB Output is correct
28 Correct 119 ms 17364 KB Output is correct
29 Correct 124 ms 17636 KB Output is correct
30 Correct 143 ms 17376 KB Output is correct
31 Correct 118 ms 17316 KB Output is correct
32 Correct 165 ms 17248 KB Output is correct
33 Correct 113 ms 17640 KB Output is correct
34 Correct 124 ms 17356 KB Output is correct
35 Correct 171 ms 17408 KB Output is correct
36 Correct 127 ms 17220 KB Output is correct
37 Correct 165 ms 17544 KB Output is correct
38 Correct 122 ms 17652 KB Output is correct
39 Correct 228 ms 19240 KB Output is correct
40 Correct 180 ms 19088 KB Output is correct
41 Correct 210 ms 18900 KB Output is correct
42 Correct 206 ms 19224 KB Output is correct