結果

問題 No.898 tri-βutree
ユーザー tarattata1tarattata1
提出日時 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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#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 2140000000
const 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0