Submission #3027587


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define SP cout<<fixed<<setprecision(10)
typedef pair<ll, int> P;
const int INF = (int) 1e9;
const int MOD = (int) 1e9 + 7;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

const int limit = 100010;
struct edge {
	int to;
	ll cost;
};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d) {
	depth[v] = d;
	for (auto &e: tree[v]) {
		if (e.to == p) continue;
		dfs(e.to, v, d + e.cost);
	}
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n;
	cin >> n;
	REP(i, n - 1) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		tree[a].push_back({b, c});
		tree[b].push_back({a, c});
	}
	
	int q, k;
	cin >> q >> k;
	k--;
	
	dfs(k, -1, 0);
	
	REP(i, q) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		cout << depth[x] + depth[y] << endl;
	}
	
	return 0;
}

Submission Info

Submission Time
Task D - Transit Tree Path
User sdub
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1047 Byte
Status AC
Exec Time 221 ms
Memory 14336 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 31
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 2560 KB
sample_02.txt AC 2 ms 2560 KB
sample_03.txt AC 2 ms 2560 KB
subtask_1_1.txt AC 2 ms 2560 KB
subtask_1_10.txt AC 109 ms 3328 KB
subtask_1_11.txt AC 3 ms 2560 KB
subtask_1_12.txt AC 11 ms 2688 KB
subtask_1_13.txt AC 36 ms 2816 KB
subtask_1_14.txt AC 2 ms 2560 KB
subtask_1_15.txt AC 4 ms 2944 KB
subtask_1_16.txt AC 218 ms 9984 KB
subtask_1_17.txt AC 214 ms 9984 KB
subtask_1_18.txt AC 221 ms 9984 KB
subtask_1_19.txt AC 214 ms 10112 KB
subtask_1_2.txt AC 3 ms 2688 KB
subtask_1_20.txt AC 209 ms 14208 KB
subtask_1_21.txt AC 208 ms 14208 KB
subtask_1_22.txt AC 207 ms 13952 KB
subtask_1_23.txt AC 208 ms 12160 KB
subtask_1_24.txt AC 202 ms 9072 KB
subtask_1_25.txt AC 200 ms 9200 KB
subtask_1_26.txt AC 203 ms 9200 KB
subtask_1_27.txt AC 201 ms 9200 KB
subtask_1_28.txt AC 206 ms 14336 KB
subtask_1_3.txt AC 119 ms 7936 KB
subtask_1_4.txt AC 2 ms 2560 KB
subtask_1_5.txt AC 144 ms 3712 KB
subtask_1_6.txt AC 22 ms 3328 KB
subtask_1_7.txt AC 121 ms 3456 KB
subtask_1_8.txt AC 2 ms 2560 KB
subtask_1_9.txt AC 83 ms 8832 KB