oj.uz

Submission #900231

# Submission time Handle Problem Language Result Execution time Memory
900231 2024-01-07T23:15:26 Z stefanneagu Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 170 ms 14176 KB 
// Iti multumesc, domnule Sparky_Master_WHC_1226 pentru optimizare memorie la suma pe lant, si la pinex cu lanturi!

// (these tricks are well-known in china)

// Sau cum ar zice un om intelept,

/*

六国破灭非兵不利战不善弊在赂秦赂秦而力亏破灭之道也或曰六国互丧率赂秦耶曰不赂者以赂者丧盖失强援不能独完故曰弊
在赂秦也秦以攻取之外小则获邑大则得城较秦之所得与战胜而得者其实百倍诸侯之所亡与战败而亡者其实亦百倍则秦之所大
欲诸侯之所大患固不在战矣思厥先祖父暴霜露斩荆棘以有尺寸之地子孙视之不甚惜举以予人如弃草芥今日割五城明日割十城
然后得一夕安寝起视四境而秦兵又至矣然则诸侯之地有限暴秦之欲无厌奉之弥繁侵之愈急故不战而强弱胜负已判矣至于颠覆
理固宜然古人云以地事秦犹抱薪救火薪不尽火不灭此言得之齐人未尝赂秦终继五国迁灭何哉与嬴而不助五国也五国既丧齐亦
不免矣燕赵之君始有远略能守其土义不赂秦是故燕虽小国而后亡斯用兵之效也至丹以荆卿为计始速祸焉赵尝五战于秦二败而三
胜后秦击赵者再李牧连却之洎牧以谗诛邯郸为郡惜其用武而不终也且燕赵处秦革灭殆尽之际可谓智力孤危战败而亡诚不得已
向使三国各爱其地齐人勿附于秦刺客不行良将犹在则胜负之数存亡之理当与秦相较或未易量呜呼以赂秦之地封天下之谋臣以
事秦之心礼天下之奇才并力西向则吾恐秦人食之不得下咽也悲夫有如此之势而为秦人积威之所劫日削月割以趋于亡为国者无
使为积威之所劫哉夫六国与秦皆诸侯其势弱于秦而犹有可以不赂而胜之之势苟以天下之大下而从六国破亡之故事是又在六国
下矣!

*/

#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 2392 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 11096 KB Output is correct
2 Correct 150 ms 13656 KB Output is correct
3 Correct 151 ms 13624 KB Output is correct
4 Correct 155 ms 13664 KB Output is correct
5 Correct 150 ms 13648 KB Output is correct
6 Correct 152 ms 13648 KB Output is correct
7 Correct 160 ms 14176 KB Output is correct
8 Correct 152 ms 13748 KB Output is correct
9 Correct 150 ms 13648 KB Output is correct
10 Correct 156 ms 13932 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9616 KB Output is correct
2 Correct 39 ms 12884 KB Output is correct
3 Correct 39 ms 12884 KB Output is correct
4 Correct 39 ms 12820 KB Output is correct
5 Correct 38 ms 12884 KB Output is correct
6 Correct 39 ms 12792 KB Output is correct
7 Correct 49 ms 12884 KB Output is correct
8 Correct 39 ms 12884 KB Output is correct
9 Correct 38 ms 12884 KB Output is correct
10 Correct 38 ms 12892 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 154 ms 11096 KB Output is correct
3 Correct 150 ms 13656 KB Output is correct
4 Correct 151 ms 13624 KB Output is correct
5 Correct 155 ms 13664 KB Output is correct
6 Correct 150 ms 13648 KB Output is correct
7 Correct 152 ms 13648 KB Output is correct
8 Correct 160 ms 14176 KB Output is correct
9 Correct 152 ms 13748 KB Output is correct
10 Correct 150 ms 13648 KB Output is correct
11 Correct 156 ms 13932 KB Output is correct
12 Correct 33 ms 9616 KB Output is correct
13 Correct 39 ms 12884 KB Output is correct
14 Correct 39 ms 12884 KB Output is correct
15 Correct 39 ms 12820 KB Output is correct
16 Correct 38 ms 12884 KB Output is correct
17 Correct 39 ms 12792 KB Output is correct
18 Correct 49 ms 12884 KB Output is correct
19 Correct 39 ms 12884 KB Output is correct
20 Correct 38 ms 12884 KB Output is correct
21 Correct 38 ms 12892 KB Output is correct
22 Correct 148 ms 12204 KB Output is correct
23 Correct 60 ms 10904 KB Output is correct
24 Correct 168 ms 13288 KB Output is correct
25 Correct 149 ms 13220 KB Output is correct
26 Correct 157 ms 13140 KB Output is correct
27 Correct 170 ms 13396 KB Output is correct
28 Correct 153 ms 13276 KB Output is correct
29 Correct 154 ms 13136 KB Output is correct
30 Correct 155 ms 13652 KB Output is correct
31 Correct 153 ms 13192 KB Output is correct