oj.uz

Submission #829427

# Submission time Handle Problem Language Result Execution time Memory
829427 2023-08-18T10:34:47 Z radaiosm7 Highway Tolls (IOI18_highway) C++17
51 / 100
 168 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, i, m, st, qi, tot, l, r, nnn;
vector<pair<int, int> > adj[90005];
long long a, b, quer, we;
int sub[90005];
int d[90005];
bool dontUse[90005];
pair<pair<int, int>, int> centroid;
bool cont;
pair<int, int> roots;
pair<int, int> dist;
pair<int, int> ans;
vector<int> marked;
vector<int> vert;

void mark(int x, int p=-1) {
  for (auto y : adj[x]) {
    if (y.X == p || dontUse[y.Y]) continue;
    marked.push_back(y.Y);
    mark(y.X, x);
  }
}

void find_dist(int x, int lookFor, int p=-1) {
  for (auto y : adj[x]) {
    if (y.X == p || dontUse[y.Y]) continue;
    d[y.X] = d[x]+1;
    
    if (d[y.X] == lookFor) {
      marked.push_back(y.Y);
      vert.push_back(y.X);
    }

    else find_dist(y.X, lookFor, x);
  }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  m = (int)U.size();
  n = N;
  fill(dontUse, dontUse+m, false);
  a = (long long)A;
  b = (long long)B;

  for (i=0; i < m; ++i) {
    adj[U[i]].push_back(make_pair(V[i], i));
    adj[V[i]].push_back(make_pair(U[i], i));
  }

  vector<int> w(m, 0);
  we = ask(w);
  tot = (int)(we/a);
  cont = true;
  st = rand()%n;
  
  l = 0;
  r = m-1;

  while (l < r) {
    int mid = (l+r)/2;
    vector<int> w(m, 0);
    for (i=0; i <= mid; ++i) w[i] = 1;
    quer = ask(w);
    if (quer > we) r = mid;
    else l = mid+1;
  }

  roots.X = U[l];
  roots.Y = V[l];
  dontUse[l] = true;

  marked.clear();
  mark(roots.X);
  for (i=0; i < m; ++i) w[i] = 0;
  for (auto v : marked) w[v] = 1;
  quer = ask(w);
  dist.X = (int)((quer-we)/(b-a));
  dist.Y = tot-dist.X-1;

  d[roots.X] = 0;
  marked.clear();
  vert.clear();

  if (dist.X == 0) vert.push_back(roots.X);
  else find_dist(roots.X, dist.X);
  l = 0;
  r = (int)marked.size()-1;

  while (l < r) {
    int mid = (l+r)/2;
    vector<int> w(m, 0);
    for (i=0; i <= mid; ++i) w[marked[i]] = 1;
    quer = ask(w);
    if (quer > we) r = mid;
    else l = mid+1;
  }

  ans.X = vert[l];

  d[roots.Y] = 0;
  marked.clear();
  vert.clear();

  if (dist.Y == 0) vert.push_back(roots.Y);
  else find_dist(roots.Y, dist.Y);
  l = 0;
  r = (int)marked.size()-1;

  while (l < r) {
    int mid = (l+r)/2;
    vector<int> w(m, 0);
    for (i=0; i <= mid; ++i) w[marked[i]] = 1;
    quer = ask(w);
    if (quer > we) r = mid;
    else l = mid+1;
  }

  ans.Y = vert[l];
  answer(ans.X, ans.Y);
}

/*
12 11 63 8242 2 11           
0 1
1 2
1 3
3 4
4 5
0 6
6 7
7 8
8 9
8 10
7 11
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 9 ms 3104 KB Output is correct
3 Correct 75 ms 8852 KB Output is correct
4 Correct 69 ms 8548 KB Output is correct
5 Correct 69 ms 8508 KB Output is correct
6 Correct 85 ms 8424 KB Output is correct
7 Correct 67 ms 8548 KB Output is correct
8 Correct 66 ms 8292 KB Output is correct
9 Correct 66 ms 8800 KB Output is correct
10 Correct 82 ms 8552 KB Output is correct
11 Correct 64 ms 9328 KB Output is correct
12 Correct 63 ms 10020 KB Output is correct
13 Correct 83 ms 8552 KB Output is correct
14 Correct 76 ms 9752 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3024 KB Output is correct
2 Correct 12 ms 3908 KB Output is correct
3 Correct 20 ms 5776 KB Output is correct
4 Correct 55 ms 9728 KB Output is correct
5 Correct 67 ms 9572 KB Output is correct
6 Correct 55 ms 13952 KB Output is correct
7 Correct 72 ms 13276 KB Output is correct
8 Correct 54 ms 11136 KB Output is correct
9 Correct 55 ms 11984 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 9 ms 3024 KB Output is correct
3 Correct 46 ms 6900 KB Output is correct
4 Correct 65 ms 8432 KB Output is correct
5 Correct 67 ms 8604 KB Output is correct
6 Correct 57 ms 8244 KB Output is correct
7 Correct 61 ms 8500 KB Output is correct
8 Correct 75 ms 8608 KB Output is correct
9 Correct 72 ms 8824 KB Output is correct
10 Correct 73 ms 8848 KB Output is correct
11 Correct 75 ms 9444 KB Output is correct
12 Correct 67 ms 9728 KB Output is correct
13 Correct 77 ms 9716 KB Output is correct
14 Correct 70 ms 9724 KB Output is correct
15 Correct 63 ms 8116 KB Output is correct
16 Correct 55 ms 7996 KB Output is correct
17 Correct 77 ms 9512 KB Output is correct
18 Correct 74 ms 9880 KB Output is correct
19 Correct 59 ms 8548 KB Output is correct
20 Correct 72 ms 8368 KB Output is correct
21 Correct 74 ms 9708 KB Output is correct
22 Correct 69 ms 9380 KB Output is correct
23 Correct 70 ms 9204 KB Output is correct
24 Correct 73 ms 9676 KB Output is correct
25 Correct 85 ms 16764 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 168 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 144 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -