oj.uz

Submission #1039708

# Submission time Handle Problem Language Result Execution time Memory
1039708 2024-07-31T08:03:25 Z NeroZein Highway Tolls (IOI18_highway) C++17
18 / 100
 262 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std; 

const int N = 1e5 + 5; 

int n, m, a, b;
vector<int> g[N]; 
int pe[N], dep[N];
long long min_dist;
vector<int> iu, iv;
int idd, pr[N], in[N], out[N];

void dfs(int v, int p) {
  in[v] = idd++; 
  for (int i : g[v]) {
    int u = iu[i] ^ iv[i] ^ v; 
    if (u == p) {
      continue; 
    }
    pe[u] = i; 
    pr[u] = v; 
    dep[u] = dep[v] + 1; 
    //cout << "u, i, dep: " << u << ' ' << i << ' ' << dep[u] << endl;
    dfs(u, v); 
  }
  out[v] = idd - 1; 
}

void dfs2(int v, int p, vector<int>& w) {
  for (int i : g[v]) {
    int u = iu[i] ^ iv[i] ^ v;
    if (u == p) {
      continue; 
    }
    w[i] = true; 
    dfs2(u, v, w); 
  }
}

bool isParent(int v, int u) {
  return in[v] <= in[u] && out[v] >= out[u];
}

int figure(vector<int>& candidates) {
  //bool deb = false; 
  //vector<int> o = {3, 4};
  //if (candidates == o) {
    //deb = true; 
  //}
  while (candidates.size() > 1) {
    vector<int> w(m, 0); 
    int s = (int) candidates.size();
    int mid = s / 2; 
    for (int i = 0; i < mid; ++i) {
      int v = candidates[i]; 
      w[pe[v]] = true; 
    }
    long long tmp = ask(w); 
    vector<int> new_candidates; 
    if (tmp == min_dist) {//lca is not among first mid elements
      for (int i = mid; i < s; ++i) {
        new_candidates.push_back(candidates[i]); 
      }
    } else {
      for (int i = 0; i < mid; ++i) {
        new_candidates.push_back(candidates[i]); 
      }
    }
    candidates = new_candidates;
  }
  return candidates[0];
}

void find_pair(int n_, vector<int> U, vector<int> V, int a_, int b_) {
  iu = U, iv = V;
  n = n_; a = a_; b = b_;
  m = (int) U.size(); 
  for (int i = 0; i < m; ++i) {
    g[U[i]].push_back(i);
    g[V[i]].push_back(i);
  }
  dfs(0, 0); 
  vector<int> w(m, 0); 
  min_dist = ask(w); 
  //lca depth is the largest depth such that if all nodes with depth <= this depth parent edges were heavy the orginal cost is not affected
  int l = 0, r = n - 1; 
  while (l < r) {
    fill(w.begin(), w.end(), 0); 
    int mid = (l + r + 1) >> 1;
    for (int i = 1; i < n; ++i) {
      if (dep[i] <= mid) {
        w[pe[i]] = 1; 
      }
    }
    long long tmp = ask(w);
    if (tmp == min_dist) {
      l = mid;
    } else {
      r = mid - 1; 
    }
  }
  int lca_depth = l; 
  //cerr << "DEP: " << lca_depth << endl; 
  vector<int> candidates; 
  for (int i = 0; i < n; ++i) {
    if (dep[i] == lca_depth) {
      candidates.push_back(i); 
    }
  }
  while (candidates.size() > 1) {
    int s = (int) candidates.size();
    int mid = s / 2; 
    fill(w.begin(), w.end(), 0); 
    for (int i = 0; i < mid; ++i) {
      int v = candidates[i];
      dfs2(v, pr[v], w); 
    }
    long long tmp = ask(w);
    vector<int> new_candidates; 
    if (tmp == min_dist) {//lca is not among first mid elements
      for (int i = mid; i < s; ++i) {
        new_candidates.push_back(candidates[i]); 
      }
    } else {
      for (int i = 0; i < mid; ++i) {
        new_candidates.push_back(candidates[i]); 
      }
    }
    candidates = new_candidates;
  }
  int lca = candidates[0];
  cerr << "LCA: " << lca << '\n'; 
  l = 0, r = (int) g[lca].size() - 1; 
  while (l < r) {
    fill(w.begin(), w.end(), 0); 
    int mid = (l + r) >> 1;
    for (int i = l; i <= mid; ++i) {
      int u = lca ^ iu[g[lca][i]] ^ iv[g[lca][i]];
      w[g[lca][i]] = true; 
      dfs2(u, lca, w); 
    }
    long long tmp = ask(w);
    if (tmp != min_dist) {
      r = mid;
    } else {
      l = mid + 1; 
    }
  }
  int ind = g[lca][l];
  //cerr << "ind: " << ind << endl; 
  int first_son_s = iu[ind] ^ iv[ind] ^ lca;
  cerr << "firstson: " << first_son_s << endl; 
  fill(w.begin(), w.end(), 0); 
  dfs2(first_son_s, lca, w); 
  int depS = dep[first_son_s] + (ask(w) - min_dist) / (b - a); 
  candidates.clear();
  for (int i = 0; i < n; ++i) {
    if (dep[i] == depS && isParent(first_son_s, i)) {
      candidates.push_back(i); 
    }
  }
  int s = figure(candidates);  
  cerr << "S: " << s << endl; 
  reverse(g[lca].begin(), g[lca].end()); 
  l = 0, r = (int) g[lca].size() - 1; 
  while (l < r) {
    fill(w.begin(), w.end(), 0); 
    int mid = (l + r) >> 1;
    for (int i = l; i <= mid; ++i) {
      int u = lca ^ iu[g[lca][i]] ^ iv[g[lca][i]];
      //cerr << "i, u: " << i << ' ' << u << endl; 
      w[g[lca][i]] = true; 
      dfs2(u, lca, w); 
    }
    long long tmp = ask(w);
    if (tmp != min_dist) {
      r = mid;
    } else {
      l = mid + 1; 
    }
  }
  ind = g[lca][l];
  //cerr << "ind: " << ind << endl; 
  int first_son_t = iu[ind] ^ iv[ind] ^ lca; 
  //cerr << "lca, first_son_t: " << lca << ' ' << first_son_t << endl; 
  fill(w.begin(), w.end(), 0); 
  dfs2(first_son_t, lca, w); 
  //int depT = dep[first_son_t] + (ask(w) - min_dist) / (b - a); 
  int depT = min_dist / a - dep[s] + dep[lca];
  candidates.clear();
  for (int i = 0; i < n; ++i) {
    if (dep[i] == depT && isParent(first_son_t, i)) {
      candidates.push_back(i); 
    }
  }
  int t = figure(candidates); 
  //cerr << "T: " << t << endl; 
  if (s == t) {
    answer(lca, s); 
  } else {
    answer(s, t); 
  }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2648 KB Output is correct
2 Correct 11 ms 3648 KB Output is correct
3 Correct 95 ms 10412 KB Output is correct
4 Correct 106 ms 10308 KB Output is correct
5 Correct 96 ms 10400 KB Output is correct
6 Correct 83 ms 10324 KB Output is correct
7 Correct 79 ms 10324 KB Output is correct
8 Correct 93 ms 10416 KB Output is correct
9 Correct 88 ms 10276 KB Output is correct
10 Correct 88 ms 10404 KB Output is correct
11 Correct 95 ms 11820 KB Output is correct
12 Correct 95 ms 12604 KB Output is correct
13 Correct 91 ms 11924 KB Output is correct
14 Correct 92 ms 11244 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4180 KB Output is correct
2 Correct 19 ms 5720 KB Output is correct
3 Correct 23 ms 7496 KB Output is correct
4 Correct 70 ms 16812 KB Output is correct
5 Correct 68 ms 16888 KB Output is correct
6 Correct 72 ms 16800 KB Output is correct
7 Correct 71 ms 17112 KB Output is correct
8 Correct 65 ms 16892 KB Output is correct
9 Correct 70 ms 16896 KB Output is correct

Subtask #4
0 / 33.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 #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 262 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 239 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -