結果

問題 No.898 tri-βutree
ユーザー tarattata1tarattata1
提出日時 2019-10-04 21:55:45
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 113 ms
30,436 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 193 ms
17,408 KB
testcase_08 AC 199 ms
17,408 KB
testcase_09 AC 193 ms
17,408 KB
testcase_10 AC 180 ms
16,896 KB
testcase_11 AC 189 ms
17,408 KB
testcase_12 AC 185 ms
17,408 KB
testcase_13 AC 188 ms
17,152 KB
testcase_14 AC 188 ms
17,280 KB
testcase_15 AC 190 ms
17,408 KB
testcase_16 AC 178 ms
17,152 KB
testcase_17 AC 191 ms
17,536 KB
testcase_18 AC 187 ms
17,152 KB
testcase_19 AC 190 ms
17,280 KB
testcase_20 AC 186 ms
17,408 KB
testcase_21 AC 187 ms
17,024 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
0