oj.uz

Submission #829421

# Submission time Handle Problem Language Result Execution time Memory
829421 2023-08-18T10:32:48 Z radaiosm7 Highway Tolls (IOI18_highway) C++17
0 / 100
 187 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 dfs_ch(int x, int p=-1) {
  sub[x] = 1;

  for (auto y : adj[x]) {
    if (y.X == p || dontUse[y.Y]) continue;
    dfs_ch(y.X, x);
    sub[x] += sub[y.X];
  }

  nnn = sub[x];
}

void find_centroid(int x, int p=-1) {
  for (auto y : adj[x]) {
    if (y.X == p || dontUse[y.Y]) continue;
    
    if (sub[y.X] >= nnn/2) {
      centroid = make_pair(make_pair(x, y.X), y.Y);
      find_centroid(y.X, x);
      break;
    }
  }
}

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];

  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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2384 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 2384 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 7 ms 4000 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 2476 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 187 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 174 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -