oj.uz

Submission #1038750

# Submission time Handle Problem Language Result Execution time Memory
1038750 2024-07-30T07:13:43 Z huutuan Highway Tolls (IOI18_highway) C++14
51 / 100
 104 ms 13752 KB 
#include "highway.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

void find_pair(int32_t N, vector<int32_t> U, vector<int32_t> V, int32_t A, int32_t B) {
   vector<vector<int>> g(N);
   for (int i=0; i<N-1; ++i) g[U[i]].push_back(i), g[V[i]].push_back(i);
   vector<pair<int, int>> order;
   vector<int32_t> a(N-1);
   int len=ask(a)/A;
   auto dfs=[&](auto &&self, int u, int p) -> void {
      for (int i:g[u]) if (i!=p){
         int v=u^U[i]^V[i];
         order.emplace_back(i, v);
         self(self, v, i);
      }
   };
   int S, T;
   {
      order.clear();
      dfs(dfs, 0, -1);
      int l=0, r=N-1;
      while (l<=r){
         int mid=(l+r)>>1;
         for (int i=0; i<=mid; ++i) a[order[i].first]=1;
         if (ask(a)==len*B) r=mid-1;
         else l=mid+1;
         for (int i=0; i<=mid; ++i) a[order[i].first]=0;
      }
      S=order[l].second;
   }
   {
      order.clear();
      dfs(dfs, S, -1);
      int l=0, r=N-1;
      while (l<=r){
         int mid=(l+r)>>1;
         for (int i=0; i<=mid; ++i) a[order[i].first]=1;
         if (ask(a)==len*B) r=mid-1;
         else l=mid+1;
         for (int i=0; i<=mid; ++i) a[order[i].first]=0;
      }
      T=order[l].second;
   }
   answer(S, T);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 9 ms 1528 KB Output is correct
3 Correct 104 ms 9692 KB Output is correct
4 Correct 101 ms 9676 KB Output is correct
5 Correct 99 ms 9692 KB Output is correct
6 Correct 97 ms 9848 KB Output is correct
7 Correct 93 ms 9928 KB Output is correct
8 Correct 76 ms 9688 KB Output is correct
9 Correct 88 ms 9672 KB Output is correct
10 Correct 93 ms 9840 KB Output is correct
11 Correct 96 ms 10436 KB Output is correct
12 Correct 80 ms 10708 KB Output is correct
13 Correct 80 ms 10436 KB Output is correct
14 Correct 82 ms 10040 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2008 KB Output is correct
2 Correct 13 ms 3284 KB Output is correct
3 Correct 18 ms 4876 KB Output is correct
4 Correct 59 ms 13752 KB Output is correct
5 Correct 58 ms 13516 KB Output is correct
6 Correct 64 ms 13520 KB Output is correct
7 Correct 64 ms 13516 KB Output is correct
8 Correct 59 ms 13752 KB Output is correct
9 Correct 62 ms 13516 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1528 KB Output is correct
3 Correct 71 ms 8028 KB Output is correct
4 Correct 88 ms 9708 KB Output is correct
5 Correct 75 ms 9676 KB Output is correct
6 Correct 76 ms 9672 KB Output is correct
7 Correct 84 ms 9688 KB Output is correct
8 Correct 74 ms 9668 KB Output is correct
9 Correct 82 ms 9704 KB Output is correct
10 Correct 69 ms 9712 KB Output is correct
11 Correct 85 ms 9924 KB Output is correct
12 Correct 85 ms 10948 KB Output is correct
13 Correct 88 ms 10692 KB Output is correct
14 Correct 89 ms 10728 KB Output is correct
15 Correct 83 ms 9692 KB Output is correct
16 Correct 66 ms 9672 KB Output is correct
17 Correct 92 ms 10704 KB Output is correct
18 Correct 73 ms 10352 KB Output is correct
19 Correct 82 ms 9680 KB Output is correct
20 Correct 69 ms 11240 KB Output is correct
21 Correct 57 ms 9832 KB Output is correct
22 Correct 59 ms 9800 KB Output is correct
23 Correct 64 ms 9916 KB Output is correct
24 Correct 79 ms 10368 KB Output is correct
25 Correct 80 ms 13076 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1112 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1112 KB Incorrect
2 Halted 0 ms 0 KB -