oj.uz

답안 #783038

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
783038 2023-07-14T14:27:11 Z Charizard2021 Roadside Advertisements (NOI17_roadsideadverts) C++17
7 / 100
 76 ms 20992 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 500001;
int dp[21][N];
vector<pair<int, int> > adj[N];
int level[N];
int dist[N];
void dfs(int u, int p){
	for(pair<int, int> x : adj[u]){
        int v = x.first;
		if(v != p){
			dp[0][v] = u;
			level[v] = level[u] + 1;
            dist[v] = dist[u] + x.second;
			dfs(v, u);
		}
	}
}
int solve(int x, int k){
	int val = 0;
	while(k > 0){
		if(k % 2 == 1){
			x = dp[val][x];
		}
		val++;
		k >>= 1;
	}
	return x;
}
int solve2(int a, int b){
	if(level[a] > level[b]){
		swap(a, b);
	}
	int difference = level[b] - level[a];
	b = solve(b, difference);
	if(a == b){
		return a;
	}
	for(int i = 20; i >= 0; i--){
		if(dp[i][a] != dp[i][b]){
			a = dp[i][a];
			b = dp[i][b];
		}
	}
	return dp[0][a];
}
int dist2(int a, int b){
    return dist[a] + dist[b] - 2 * dist[solve2(a, b)];
}
int main(){
    int n;
    cin >> n;
	for(int i = 0; i < n - 1; i++){
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back(make_pair(b, c));
		adj[b].push_back(make_pair(a, c));
	}
    dist[0] = 0;
	dfs(0, -1);
	for(int i = 1; i < 21; i++){
		for(int j = 0; j < n; j++){
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
		}
	}
    int q;
    cin >> q;
	while(q--){
        int 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 6 ms 12184 KB Output is correct

Subtask #2
0 / 23.0

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

Subtask #3
0 / 40.0

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

Subtask #4
0 / 30.0

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