oj.uz

Submission #1039702

# Submission time Handle Problem Language Result Execution time Memory
1039702 2024-07-31T07:59:15 Z NeroZein Highway Tolls (IOI18_highway) C++17
18 / 100
 309 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); 
  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 1 ms 2648 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 2 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 1 ms 2648 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2640 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 2 ms 2648 KB Output is correct
2 Correct 9 ms 3416 KB Output is correct
3 Correct 122 ms 10580 KB Output is correct
4 Correct 91 ms 10404 KB Output is correct
5 Correct 92 ms 10472 KB Output is correct
6 Correct 101 ms 10328 KB Output is correct
7 Correct 87 ms 10360 KB Output is correct
8 Correct 98 ms 10412 KB Output is correct
9 Correct 94 ms 10288 KB Output is correct
10 Correct 102 ms 10608 KB Output is correct
11 Correct 91 ms 11864 KB Output is correct
12 Correct 95 ms 12720 KB Output is correct
13 Correct 102 ms 11984 KB Output is correct
14 Correct 98 ms 11256 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4184 KB Output is correct
2 Correct 15 ms 5932 KB Output is correct
3 Correct 23 ms 7492 KB Output is correct
4 Correct 68 ms 16888 KB Output is correct
5 Correct 66 ms 16884 KB Output is correct
6 Correct 70 ms 16900 KB Output is correct
7 Correct 80 ms 16892 KB Output is correct
8 Correct 69 ms 16892 KB Output is correct
9 Correct 64 ms 16892 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 9 ms 3612 KB Output is correct
3 Correct 74 ms 8600 KB Output is correct
4 Correct 99 ms 10376 KB Output is correct
5 Correct 85 ms 10356 KB Output is correct
6 Correct 87 ms 10356 KB Output is correct
7 Correct 84 ms 10492 KB Output is correct
8 Correct 91 ms 10272 KB Output is correct
9 Correct 110 ms 10360 KB Output is correct
10 Correct 106 ms 10220 KB Output is correct
11 Correct 108 ms 11252 KB Output is correct
12 Correct 122 ms 12704 KB Output is correct
13 Correct 118 ms 12064 KB Output is correct
14 Correct 111 ms 12648 KB Output is correct
15 Correct 104 ms 10224 KB Output is correct
16 Correct 96 ms 10060 KB Output is correct
17 Correct 124 ms 12508 KB Output is correct
18 Correct 108 ms 11864 KB Output is correct
19 Correct 99 ms 10268 KB Output is correct
20 Correct 104 ms 12928 KB Output is correct
21 Correct 76 ms 10212 KB Output is correct
22 Correct 75 ms 10196 KB Output is correct
23 Incorrect 103 ms 10904 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 309 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 -