oj.uz

Submission #946663

# Submission time Handle Problem Language Result Execution time Memory
946663 2024-03-14T21:24:59 Z PagodePaiva Highway Tolls (IOI18_highway) C++17
12 / 100
 202 ms 31788 KB 
#include "highway.h"
#include<bits/stdc++.h>
#define N 90010
#define ll long long

using namespace std;

vector <int> g[N];
int dist[N];
int pai[N];
map <pair <int, int>, int> m;
vector <int> distantes[N];
// int pai[N];

void dfs(int v, int p){
  distantes[dist[v]].push_back(v);
  pai[v] = p;
  for(auto x : g[v]){
    if(x == p) continue;
    dist[x] = dist[v] + 1;
    dfs(x,v);
  }
}

void find_pair(int n, std::vector<int> u, std::vector<int> v, int an, int bn) {
  ll a = an;
  ll b = bn;
  for(int i = 0;i < n-1;i++){
    g[u[i]].push_back(v[i]);
    g[v[i]].push_back(u[i]);
    m[{u[i], v[i]}] = i;
    m[{v[i], u[i]}] = i;
  }
  dfs(0, 0);
  int t = u.size();
  vector <int> w(t);
  for(int i = 0;i < t;i++){
    w[i] = 0;
  } 
  ll preco = ask(w);
  ll D = preco/a;
  int l = 0, r = (int) (distantes[D].size())-1;
  while(l < r){
    int mid = (l+r)/2;
    for(int i = l;i <= mid;i++) w[m[{distantes[D][i], pai[distantes[D][i]]}]] = 1;
    preco = ask(w);
    if(preco == D*a){
      l = mid+1;
    }
    else{
      r = mid;
    }
    for(int i = 0;i < n-1;i++) w[i] = 0;
  }
  answer(0, distantes[D][l]);
  return;
  // int M = U.size();
  // for (int j = 0; j < 50; ++j) {
  //   std::vector<int> w(M);
  //   for (int i = 0; i < M; ++i) {
  //     w[i] = 0;
  //   }
  //   long long toll = ask(w);
  // }
  // answer(0, N - 1);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:27:6: warning: unused variable 'b' [-Wunused-variable]
   27 |   ll b = bn;
      |      ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5464 KB Output is correct
2 Correct 20 ms 6992 KB Output is correct
3 Correct 174 ms 21952 KB Output is correct
4 Correct 202 ms 21860 KB Output is correct
5 Correct 165 ms 21844 KB Output is correct
6 Correct 158 ms 21808 KB Output is correct
7 Correct 159 ms 21868 KB Output is correct
8 Correct 181 ms 22160 KB Output is correct
9 Correct 147 ms 21892 KB Output is correct
10 Correct 149 ms 21856 KB Output is correct
11 Correct 155 ms 23484 KB Output is correct
12 Correct 146 ms 24332 KB Output is correct
13 Correct 149 ms 23608 KB Output is correct
14 Correct 151 ms 22924 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 8024 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 2 ms 5464 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 Runtime error 37 ms 31244 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 31788 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -