oj.uz

Submission #1016334

# Submission time Handle Problem Language Result Execution time Memory
1016334 2024-07-07T20:13:34 Z cadmiumsky Highway Tolls (IOI18_highway) C++17
90 / 100
 197 ms 15132 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);
}

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_ ;
   int root = -1;
   
   for(int step = 16; step >= 0; step--) {
      if(root + (1 << step) >= N) continue;
      int cand = root + (1 << step);
      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;
   }
   
   root++;
   
   //cerr << root << '\n';

   vector<int> list, p(N, -1);
   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;
      }
      list.emplace_back(node);
      for(auto [x, e] : g[node]) {
         if(p[x] == -1)
            p[x] = node, que.emplace(x);
      }
   }
   
   int S = sz(list);
   for(int i = 16; i >= 0; i--) {
      if(S - (1 << i) < 0) continue;
      int cand = S - (1 << i);
      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 -= (1 << i);
   }
   
   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';
   
   int T = sz(list);
   for(int i = 16; i >= 0; i--) {
      if(T - (1 << i) < 0) continue;
      int cand = T - (1 << i);
      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 -= (1 << i);
   }
   
   T = list[T - 1];
   //cerr << T << '\n';
   
   answer(S, T);
   return;
}
#undef int

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:34:8: warning: unused variable 'lenght' [-Wunused-variable]
   34 |    int lenght = standard_ ;
      |        ^~~~~~

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 2648 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 2 ms 2648 KB Output is correct
2 Correct 13 ms 3860 KB Output is correct
3 Correct 141 ms 12012 KB Output is correct
4 Correct 156 ms 12044 KB Output is correct
5 Correct 131 ms 12036 KB Output is correct
6 Correct 128 ms 11972 KB Output is correct
7 Correct 130 ms 12048 KB Output is correct
8 Correct 162 ms 12044 KB Output is correct
9 Correct 151 ms 12160 KB Output is correct
10 Correct 137 ms 12028 KB Output is correct
11 Correct 131 ms 11640 KB Output is correct
12 Correct 135 ms 11416 KB Output is correct
13 Correct 137 ms 11420 KB Output is correct
14 Correct 121 ms 11404 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4028 KB Output is correct
2 Correct 26 ms 4732 KB Output is correct
3 Correct 33 ms 5412 KB Output is correct
4 Correct 112 ms 11184 KB Output is correct
5 Correct 97 ms 11216 KB Output is correct
6 Correct 99 ms 11316 KB Output is correct
7 Correct 99 ms 10796 KB Output is correct
8 Correct 104 ms 11232 KB Output is correct
9 Correct 107 ms 10896 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 13 ms 3876 KB Output is correct
3 Correct 98 ms 10072 KB Output is correct
4 Correct 128 ms 11840 KB Output is correct
5 Correct 126 ms 12008 KB Output is correct
6 Correct 107 ms 11316 KB Output is correct
7 Correct 121 ms 11812 KB Output is correct
8 Correct 125 ms 11684 KB Output is correct
9 Correct 135 ms 11904 KB Output is correct
10 Correct 145 ms 12012 KB Output is correct
11 Correct 128 ms 10896 KB Output is correct
12 Correct 135 ms 11380 KB Output is correct
13 Correct 135 ms 11248 KB Output is correct
14 Correct 129 ms 11220 KB Output is correct
15 Correct 128 ms 12072 KB Output is correct
16 Correct 125 ms 11568 KB Output is correct
17 Correct 134 ms 11224 KB Output is correct
18 Correct 120 ms 10896 KB Output is correct
19 Correct 94 ms 11248 KB Output is correct
20 Correct 102 ms 10820 KB Output is correct
21 Correct 129 ms 12676 KB Output is correct
22 Correct 128 ms 12596 KB Output is correct
23 Correct 113 ms 12260 KB Output is correct
24 Correct 115 ms 12168 KB Output is correct
25 Correct 131 ms 11532 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3824 KB Output is correct
2 Correct 14 ms 3936 KB Output is correct
3 Correct 146 ms 12584 KB Output is correct
4 Correct 162 ms 13028 KB Output is correct
5 Correct 191 ms 14416 KB Output is correct
6 Correct 191 ms 14396 KB Output is correct
7 Correct 197 ms 14400 KB Output is correct
8 Correct 196 ms 14620 KB Output is correct
9 Correct 145 ms 11540 KB Output is correct
10 Correct 133 ms 12056 KB Output is correct
11 Correct 141 ms 12220 KB Output is correct
12 Correct 186 ms 13896 KB Output is correct
13 Correct 157 ms 14664 KB Output is correct
14 Correct 167 ms 14456 KB Output is correct
15 Correct 164 ms 15044 KB Output is correct
16 Correct 145 ms 12860 KB Output is correct
17 Correct 109 ms 12272 KB Output is correct
18 Correct 127 ms 12652 KB Output is correct
19 Correct 117 ms 12508 KB Output is correct
20 Correct 121 ms 12400 KB Output is correct
21 Correct 170 ms 14872 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3884 KB Output is correct
2 Correct 15 ms 3888 KB Output is correct
3 Correct 153 ms 12892 KB Output is correct
4 Correct 149 ms 12836 KB Output is correct
5 Correct 157 ms 12972 KB Output is correct
6 Correct 192 ms 15020 KB Output is correct
7 Correct 155 ms 12432 KB Output is correct
8 Correct 151 ms 12848 KB Output is correct
9 Correct 144 ms 13280 KB Output is correct
10 Correct 188 ms 14396 KB Output is correct
11 Correct 190 ms 14428 KB Output is correct
12 Correct 175 ms 14512 KB Output is correct
13 Correct 151 ms 12440 KB Output is correct
14 Correct 159 ms 12080 KB Output is correct
15 Correct 168 ms 12580 KB Output is correct
16 Correct 138 ms 12096 KB Output is correct
17 Correct 142 ms 12100 KB Output is correct
18 Correct 146 ms 12156 KB Output is correct
19 Correct 188 ms 14128 KB Output is correct
20 Correct 154 ms 14112 KB Output is correct
21 Correct 191 ms 15132 KB Output is correct
22 Correct 175 ms 14920 KB Output is correct
23 Correct 159 ms 15072 KB Output is correct
24 Correct 191 ms 14432 KB Output is correct
25 Correct 159 ms 14444 KB Output is correct
26 Correct 171 ms 14516 KB Output is correct
27 Correct 127 ms 12548 KB Output is correct
28 Correct 120 ms 12432 KB Output is correct
29 Correct 131 ms 12492 KB Output is correct
30 Correct 108 ms 12248 KB Output is correct
31 Correct 112 ms 12460 KB Output is correct
32 Correct 118 ms 12148 KB Output is correct
33 Correct 114 ms 12668 KB Output is correct
34 Correct 109 ms 12524 KB Output is correct
35 Correct 116 ms 12580 KB Output is correct
36 Correct 128 ms 12372 KB Output is correct
37 Correct 124 ms 12416 KB Output is correct
38 Correct 121 ms 12380 KB Output is correct
39 Correct 179 ms 14444 KB Output is correct
40 Correct 157 ms 14924 KB Output is correct
41 Partially correct 173 ms 14400 KB Output is partially correct
42 Correct 167 ms 14876 KB Output is correct