oj.uz

Submission #900232

# Submission time Handle Problem Language Result Execution time Memory
900232 2024-01-07T23:16:06 Z stefanneagu Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 164 ms 12952 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 1;

vector<vector<pair<int, int>>> adj;
int u[nmax][17], d[nmax], e[nmax], depth[nmax], v[6], fin, cnt = 1;

void dfs(int i, int tata) {
  u[i][0] = tata;
  e[i] = cnt;
  cnt ++;
  for(auto it : adj[i]) {
    if(it.first != tata) {
      d[it.first] = d[i] + it.second;
      depth[it.first] = depth[i] + 1;
      dfs(it.first, i);
    }
  }
}

int get(int a, int x) {
  for(int i = 0; (1 << i) <= x; i ++) {
    if((1 << i) & x) {
      a = u[a][i];
    }
  }
  return a;
}

int lca(int a, int b) {
  if(depth[a] > depth[b]) {
    swap(a, b);
  }
  int l = 0, r = depth[a], ans = 0;
  while(l <= r) {
    int mid = (l + r) / 2;
    if(get(a, mid) == get(b, mid + depth[b] - depth[a])) {
      ans = get(a, mid);
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  return ans;
}

int sum(int x, int y) {
  return d[x] + d[y] - 2 * d[lca(x, y)];
}

bool cmp(int a, int b) {
  return e[a] < e[b];
}

void testcase() {
  for(int i = 1; i <= 5; i ++) {
    cin >> v[i];
    v[i] ++;
  }
  sort(v + 1, v + 6, cmp);
  int ans = sum(lca(v[1], v[5]), v[1]);
  for(int i = 2; i <= 5; i ++) {
    ans += sum(lca(v[i - 1], v[i]), v[i]);
  }
  //assert(ans == fin);
  cout << ans << '\n';
}

int main() {
  int n;
  cin >> n;
  adj.resize(n + 1);
  for(int i = 1; i < n; i ++) {
    int a, b, c;
    cin >> a >> b >> c;
    a ++, b ++;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
    fin += c;
  }
  dfs(1, 0);
  for(int j = 1; (1 << j) <= n; j ++) {
    for(int i = 1; i <= n; i ++) {
      if(depth[i] >= (1 << j)) {
        u[i][j] = u[u[i][j - 1]][j - 1];
      }
    }
  }
  int q;
  cin >> q;
  for(int tt = 1; tt <= q; tt ++) {
    testcase();
  }
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 11180 KB Output is correct
2 Correct 148 ms 12668 KB Output is correct
3 Correct 158 ms 12952 KB Output is correct
4 Correct 150 ms 12644 KB Output is correct
5 Correct 152 ms 12692 KB Output is correct
6 Correct 149 ms 12880 KB Output is correct
7 Correct 149 ms 12544 KB Output is correct
8 Correct 151 ms 12628 KB Output is correct
9 Correct 157 ms 12688 KB Output is correct
10 Correct 149 ms 12624 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9784 KB Output is correct
2 Correct 37 ms 11940 KB Output is correct
3 Correct 38 ms 12116 KB Output is correct
4 Correct 38 ms 12112 KB Output is correct
5 Correct 38 ms 12124 KB Output is correct
6 Correct 40 ms 12112 KB Output is correct
7 Correct 38 ms 12120 KB Output is correct
8 Correct 38 ms 12056 KB Output is correct
9 Correct 51 ms 12112 KB Output is correct
10 Correct 51 ms 11988 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 145 ms 11180 KB Output is correct
3 Correct 148 ms 12668 KB Output is correct
4 Correct 158 ms 12952 KB Output is correct
5 Correct 150 ms 12644 KB Output is correct
6 Correct 152 ms 12692 KB Output is correct
7 Correct 149 ms 12880 KB Output is correct
8 Correct 149 ms 12544 KB Output is correct
9 Correct 151 ms 12628 KB Output is correct
10 Correct 157 ms 12688 KB Output is correct
11 Correct 149 ms 12624 KB Output is correct
12 Correct 34 ms 9784 KB Output is correct
13 Correct 37 ms 11940 KB Output is correct
14 Correct 38 ms 12116 KB Output is correct
15 Correct 38 ms 12112 KB Output is correct
16 Correct 38 ms 12124 KB Output is correct
17 Correct 40 ms 12112 KB Output is correct
18 Correct 38 ms 12120 KB Output is correct
19 Correct 38 ms 12056 KB Output is correct
20 Correct 51 ms 12112 KB Output is correct
21 Correct 51 ms 11988 KB Output is correct
22 Correct 140 ms 11088 KB Output is correct
23 Correct 75 ms 9884 KB Output is correct
24 Correct 148 ms 12200 KB Output is correct
25 Correct 153 ms 12196 KB Output is correct
26 Correct 150 ms 12172 KB Output is correct
27 Correct 150 ms 12116 KB Output is correct
28 Correct 164 ms 12544 KB Output is correct
29 Correct 149 ms 12184 KB Output is correct
30 Correct 154 ms 12116 KB Output is correct
31 Correct 150 ms 12112 KB Output is correct