제출 #900224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
900224		stefanneagu	Roadside Advertisements (NOI17_roadsideadverts)	C++17	0 / 100	49 ms	22996 KiB

roadsideadverts

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

void dfs(int i, int tata, int cnt) {
  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, cnt);
    }
  }
}

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, 1);
  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: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 40
• Subtask 4: 0 / 30