結果
問題 | No.898 tri-βutree |
ユーザー |
![]() |
提出日時 | 2019-10-04 21:55:45 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 199 ms / 4,000 ms |
コード長 | 2,437 bytes |
コンパイル時間 | 1,203 ms |
コンパイル使用メモリ | 85,356 KB |
実行使用メモリ | 30,436 KB |
最終ジャッジ日時 | 2024-11-08 22:02:59 |
合計ジャッジ時間 | 6,275 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’: main.cpp:88:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 88 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:99:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 99 | scanf("%d%d%d", &a, &b, &c); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~ main.cpp:109:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 109 | scanf("%d", &Q); | ~~~~~^~~~~~~~~~ main.cpp:113:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 113 | scanf("%d%d%d", &x, &y, &z); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <stdio.h>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <algorithm>#include <vector>#include <set>#include <map>#include <queue>#include <stack>#include <list>#include <iterator>#include <assert.h>#pragma warning(disable:4996)typedef long long ll;#define MIN(a, b) ((a)>(b)? (b): (a))#define MAX(a, b) ((a)<(b)? (b): (a))#define LINF 9223300000000000000#define INF 2140000000const long long MOD = 1000000007;using namespace std;vector<int> vis;vector<int> depth;vector<ll> sumw;vector<vector<pair<int,int> > > g;vector<vector<int> > anc;void dfs( int curr, ll currw, vector<int>& vv ){vis[curr]=1;depth[curr]=(int)vv.size();sumw[curr]=currw;int k=1;while(k<=depth[curr]) {anc[curr].push_back(vv[depth[curr]-k]);k*=2;}vv.push_back( curr );int i;for(i=0; i<(int)g[curr].size(); i++) {if( !vis[g[curr][i].first] ) {dfs( g[curr][i].first, currw+g[curr][i].second, vv );}}vv.pop_back();return;}int getanc( int a, int b ){if(depth[a]>depth[b]) swap(a, b);int delta = depth[b]-depth[a];int cnt=0;while(delta>0) {if(delta & (1<<cnt)) {b = anc[b][cnt];delta -= (1<<cnt);}cnt++;}assert(depth[a]==depth[b]);if(a==b) return a;int N=(int)anc[a].size();int i;for(i=N-1; i>=0; i--) {if((int)anc[a].size()>i) {if(anc[a][i]!=anc[b][i]) {a = anc[a][i];b = anc[b][i];}}}return anc[a][0];}int main(int argc, char* argv[]){int n;scanf("%d", &n);vis.resize(n);g.resize(n);depth.resize(n);sumw.resize(n);anc.resize(n);int i;for(i=0; i<n-1; i++) {int a,b,c;scanf("%d%d%d", &a, &b, &c);g[a].push_back(make_pair(b,c));g[b].push_back(make_pair(a,c));}vector<int> vv;dfs(0, 0, vv);int Q;scanf("%d", &Q);int q;for(q=0; q<Q; q++) {int x,y,z;scanf("%d%d%d", &x, &y, &z);ll ans = sumw[x] + sumw[y] + sumw[z];int tmp0=getanc(x,y);int tmp1=getanc(y,z);int tmp2=getanc(z,x);ll ans0 = sumw[tmp0]+sumw[tmp1]+sumw[tmp2];ans = ans - ans0;printf("%lld\n", ans);}return 0;}