oj.uz

답안 #783048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
783048 2023-07-14T14:30:48 Z Charizard2021 Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 66 ms 12900 KB 
#include<bits/stdc++.h>
using namespace std;
const long long N = 50001;
long long dp[17][N];
vector<pair<long long, long long> > adj[N];
long long level[N];
long long dist[N];
void dfs(long long u, long long p){
	for(pair<long long, long long> x : adj[u]){
        long long v = x.first;
		if(v != p){
			dp[0][v] = u;
			level[v] = level[u] + 1;
            dist[v] = dist[u] + x.second;
			dfs(v, u);
		}
	}
}
long long solve(long long x, long long k){
	long long val = 0;
	while(k > 0){
		if(k % 2 == 1){
			x = dp[val][x];
		}
		val++;
		k >>= 1;
	}
	return x;
}
long long solve2(long long a, long long b){
	if(level[a] > level[b]){
		swap(a, b);
	}
	long long difference = level[b] - level[a];
	b = solve(b, difference);
	if(a == b){
		return a;
	}
	for(long long i = 16; i >= 0; i--){
		if(dp[i][a] != dp[i][b]){
			a = dp[i][a];
			b = dp[i][b];
		}
	}
	return dp[0][a];
}
long long dist2(long long a, long long b){
    return dist[a] + dist[b] - 2 * dist[solve2(a, b)];
}
int main(){
    long long n;
    cin >> n;
	for(long long i = 0; i < n - 1; i++){
		long long a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, c));
	}
	dfs(0, -1);
	for(long long i = 1; i < 17; i++){
		for(long long j = 0; j < n; j++){
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
		}
	}
    long long q;
    cin >> q;
	while(q--){
        long long a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        cout << (dist2(a, b) + dist2(b, c) + dist2(c, d) + dist2(d, e) + dist2(e, a))/2 << "\n";
	}
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 66 ms 12900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 11340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Incorrect 66 ms 12900 KB Output isn't correct
3 Halted 0 ms 0 KB -