oj.uz

Submission #1016332

# Submission time Handle Problem Language Result Execution time Memory
1016332 2024-07-07T20:07:20 Z cadmiumsky Highway Tolls (IOI18_highway) C++17
0 / 100
 15 ms 3972 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++;

   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] = root, 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 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];
   
   vector<int> exonerate(N, 0);
   int tmp = S;
   while(tmp != root) exonerate[tmp] = 1, tmp = p[tmp];
   
   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 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];
   
   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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2648 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3804 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 3972 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 3856 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -