oj.uz

Submission #1016631

# Submission time Handle Problem Language Result Execution time Memory
1016631 2024-07-08T09:31:49 Z cadmiumsky Highway Tolls (IOI18_highway) C++17
100 / 100
 204 ms 17992 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

#include "highway.h"
#define int ll

const int nmax = 1e5 + 5;
vector<pii> g[nmax];

int N, M;
int Ask(vector<int> a) {
   vector<signed> b;
   for(auto x : a) b.emplace_back(x);
   return ask(b);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void find_pair(signed n__, std::vector<signed> U, std::vector<signed> V, signed A_cost, signed B_cost) {
   N = n__;
   M = sz(U);
   for(int i = 0; i < sz(U); i++) 
      g[U[i]].emplace_back(V[i], i),
      g[V[i]].emplace_back(U[i], i);
   
   int standard_ = Ask(vector<int>(M, 0));
   int lenght = standard_ / A_cost;
   int root = -1, r = N;
   while(root + 1 < r) {
      int cand = (root + r) / 2;
      if(cand >= N) continue;
      vector<int> A(M, 0);
      for(int i = 0; i <= cand; i++)
         for(auto [x, e] : g[i])
            A[e] = 1;
      if(Ask(A) == standard_)
         root = cand;
      else
         r = cand;
   }
   
   root++;
   
   //cerr << root << '\n';

   vector<int> list, p(N, -1);
   vector<int> arriv(N, 0);
   vector<vector<int>> bydist(N, vector<int>());
   queue<int> que;
   que.emplace(root);
   p[root] = root;
   while(!que.empty()) {
      int node = que.front();
      que.pop();
      if(node < root) {
         p[node] = -1;
         continue;
      }
      
      bydist[arriv[node]].emplace_back(node);
      
      list.emplace_back(node);
      shuffle(all(g[node]), rng);
      for(auto [x, e] : g[node]) {
         if(p[x] == -1)
            p[x] = node, que.emplace(x),
            arriv[x] = arriv[node] + 1;
      }
   }
   
   int S = sz(list), l = 0;
   while(l + 1 < S) {
      int cand = (S + l) / 2;
      if(cand < 0) continue;
      vector<int> A(M, 0);
      for(int i = 0; i < root; i++) 
         for(auto [x, e] : g[i])
            A[e] = 1;
      for(int a = cand; a < sz(list); a++)
         for(auto [x, e] : g[list[a]])
            A[e] = 1;
      if(Ask(A) == standard_) S = cand;
      else l = cand;
   }
   
   S--;
   S = list[S];
   
   //cerr << S << '\n';
   
   vector<int> exonerate(N, 0);
   int tmp = S;
   while(tmp != root) exonerate[tmp] = 1, tmp = p[tmp];
   //cerr << '\n';
   
   list = move(bydist[lenght - arriv[S]]);
   
   int T = sz(list); l = 0;
   while(l + 1 < T) {
      int cand = (T + l) / 2;
      if(cand < 0) continue;
      vector<int> A(M, 0);
      for(int i = 0; i < root; i++) 
         for(auto [x, e] : g[i])
            A[e] = 1;
      for(int a = cand; a < sz(list); a++)
         if(!exonerate[list[a]])
            for(auto [x, e] : g[list[a]])
               A[e] = 1;
      if(Ask(A) == standard_) T = cand;
      else l = cand;
   }
   
   T = list[T - 1];
   
   answer(S, T);
   return;
}
#undef int

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 10 ms 4180 KB Output is correct
3 Correct 112 ms 15300 KB Output is correct
4 Correct 122 ms 15280 KB Output is correct
5 Correct 116 ms 15340 KB Output is correct
6 Correct 106 ms 15192 KB Output is correct
7 Correct 119 ms 15504 KB Output is correct
8 Correct 117 ms 15264 KB Output is correct
9 Correct 112 ms 15340 KB Output is correct
10 Correct 115 ms 15344 KB Output is correct
11 Correct 113 ms 14824 KB Output is correct
12 Correct 114 ms 14972 KB Output is correct
13 Correct 114 ms 14900 KB Output is correct
14 Correct 126 ms 14756 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4272 KB Output is correct
2 Correct 24 ms 5680 KB Output is correct
3 Correct 28 ms 6248 KB Output is correct
4 Correct 89 ms 15028 KB Output is correct
5 Correct 88 ms 15040 KB Output is correct
6 Correct 92 ms 15692 KB Output is correct
7 Correct 91 ms 13020 KB Output is correct
8 Correct 95 ms 15296 KB Output is correct
9 Correct 105 ms 13732 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 11 ms 4196 KB Output is correct
3 Correct 95 ms 12364 KB Output is correct
4 Correct 137 ms 14416 KB Output is correct
5 Correct 127 ms 14832 KB Output is correct
6 Correct 101 ms 14300 KB Output is correct
7 Correct 112 ms 14196 KB Output is correct
8 Correct 117 ms 14396 KB Output is correct
9 Correct 130 ms 15112 KB Output is correct
10 Correct 119 ms 15388 KB Output is correct
11 Correct 106 ms 13836 KB Output is correct
12 Correct 115 ms 14532 KB Output is correct
13 Correct 109 ms 14572 KB Output is correct
14 Correct 112 ms 14736 KB Output is correct
15 Correct 114 ms 14948 KB Output is correct
16 Correct 111 ms 14336 KB Output is correct
17 Correct 104 ms 14696 KB Output is correct
18 Correct 105 ms 13880 KB Output is correct
19 Correct 91 ms 13276 KB Output is correct
20 Correct 104 ms 13660 KB Output is correct
21 Correct 125 ms 15148 KB Output is correct
22 Correct 107 ms 15004 KB Output is correct
23 Correct 115 ms 15656 KB Output is correct
24 Correct 123 ms 15592 KB Output is correct
25 Correct 122 ms 16088 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4248 KB Output is correct
2 Correct 12 ms 4316 KB Output is correct
3 Correct 133 ms 15608 KB Output is correct
4 Correct 165 ms 16180 KB Output is correct
5 Correct 172 ms 17772 KB Output is correct
6 Correct 179 ms 17640 KB Output is correct
7 Correct 170 ms 17544 KB Output is correct
8 Correct 188 ms 17816 KB Output is correct
9 Correct 130 ms 12436 KB Output is correct
10 Correct 136 ms 12680 KB Output is correct
11 Correct 128 ms 13268 KB Output is correct
12 Correct 172 ms 16108 KB Output is correct
13 Correct 150 ms 17064 KB Output is correct
14 Correct 182 ms 17556 KB Output is correct
15 Correct 168 ms 17800 KB Output is correct
16 Correct 143 ms 14068 KB Output is correct
17 Correct 131 ms 15344 KB Output is correct
18 Correct 120 ms 15600 KB Output is correct
19 Correct 116 ms 15344 KB Output is correct
20 Correct 121 ms 15432 KB Output is correct
21 Correct 153 ms 17688 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4264 KB Output is correct
2 Correct 13 ms 4368 KB Output is correct
3 Correct 138 ms 15476 KB Output is correct
4 Correct 149 ms 16132 KB Output is correct
5 Correct 153 ms 16024 KB Output is correct
6 Correct 177 ms 17940 KB Output is correct
7 Correct 142 ms 15624 KB Output is correct
8 Correct 137 ms 15988 KB Output is correct
9 Correct 144 ms 16336 KB Output is correct
10 Correct 204 ms 17992 KB Output is correct
11 Correct 175 ms 17656 KB Output is correct
12 Correct 190 ms 17636 KB Output is correct
13 Correct 136 ms 13488 KB Output is correct
14 Correct 137 ms 13068 KB Output is correct
15 Correct 137 ms 13564 KB Output is correct
16 Correct 129 ms 12924 KB Output is correct
17 Correct 139 ms 13212 KB Output is correct
18 Correct 139 ms 13124 KB Output is correct
19 Correct 166 ms 16420 KB Output is correct
20 Correct 162 ms 17200 KB Output is correct
21 Correct 183 ms 17432 KB Output is correct
22 Correct 157 ms 17388 KB Output is correct
23 Correct 174 ms 17892 KB Output is correct
24 Correct 170 ms 17576 KB Output is correct
25 Correct 155 ms 17052 KB Output is correct
26 Correct 177 ms 17724 KB Output is correct
27 Correct 126 ms 15320 KB Output is correct
28 Correct 113 ms 15388 KB Output is correct
29 Correct 121 ms 15432 KB Output is correct
30 Correct 133 ms 15164 KB Output is correct
31 Correct 111 ms 15172 KB Output is correct
32 Correct 115 ms 15212 KB Output is correct
33 Correct 110 ms 15616 KB Output is correct
34 Correct 129 ms 15348 KB Output is correct
35 Correct 121 ms 15384 KB Output is correct
36 Correct 119 ms 15180 KB Output is correct
37 Correct 116 ms 15336 KB Output is correct
38 Correct 151 ms 15340 KB Output is correct
39 Correct 165 ms 17724 KB Output is correct
40 Correct 164 ms 17740 KB Output is correct
41 Correct 151 ms 17736 KB Output is correct
42 Correct 180 ms 17988 KB Output is correct