oj.uz

Submission #1038746

# Submission time Handle Problem Language Result Execution time Memory
1038746 2024-07-30T07:12:32 Z huutuan Highway Tolls (IOI18_highway) C++14
5 / 100
 121 ms 11864 KB 
#include "highway.h"

#include <bits/stdc++.h>

using namespace std;

void find_pair(int N, vector<int> U, vector<int> V, int A, int 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<int> 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 0 ms 344 KB Output is correct
7 Correct 1 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 0 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 10 ms 1388 KB Output is correct
3 Correct 102 ms 8132 KB Output is correct
4 Correct 95 ms 8168 KB Output is correct
5 Correct 99 ms 8136 KB Output is correct
6 Correct 102 ms 8292 KB Output is correct
7 Correct 89 ms 8444 KB Output is correct
8 Correct 98 ms 8148 KB Output is correct
9 Correct 109 ms 8348 KB Output is correct
10 Correct 92 ms 8216 KB Output is correct
11 Correct 121 ms 8904 KB Output is correct
12 Correct 101 ms 9268 KB Output is correct
13 Correct 96 ms 9176 KB Output is correct
14 Incorrect 104 ms 8664 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1624 KB Output is correct
2 Correct 15 ms 2888 KB Output is correct
3 Correct 22 ms 4052 KB Output is correct
4 Correct 60 ms 11400 KB Output is correct
5 Correct 82 ms 11400 KB Output is correct
6 Correct 66 ms 11396 KB Output is correct
7 Correct 68 ms 11864 KB Output is correct
8 Correct 84 ms 11408 KB Output is correct
9 Incorrect 86 ms 11412 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 8 ms 1416 KB Output is correct
3 Correct 66 ms 6856 KB Output is correct
4 Correct 88 ms 8152 KB Output is correct
5 Correct 86 ms 8264 KB Output is correct
6 Correct 84 ms 8152 KB Output is correct
7 Correct 82 ms 8252 KB Output is correct
8 Correct 79 ms 8392 KB Output is correct
9 Incorrect 89 ms 8276 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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