oj.uz

Submission #731815

# Submission time Handle Problem Language Result Execution time Memory
731815 2023-04-28T03:24:10 Z Trunkty Roadside Advertisements (NOI17_roadsideadverts) C++14
7 / 100
 260 ms 29312 KB 
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,q;
vector<vector<int>> roads[50005];
int jump[50005][21],dist[50005][21],dep[50005];
int curr=0;

void dfs(int x, int p){
    for(vector<int> i:roads[x]){
        if(i[0]!=p){
            jump[i[0]][0] = x;
            dist[i[0]][0] = i[1];
            dep[i[0]] = dep[x]+1;
            dfs(i[0],x);
        }
    }
}

int lca(int a, int b){
    curr = 0;
    if(dep[a]>dep[b]){
        swap(a,b);
    }
    for(int j=20;j>=0;j--){
        if(dep[b]-(1<<j)>=dep[a]){
            curr += dist[b][j];
            b = jump[b][j];
        }
    }
    if(a==b){
        return a;
    }
    for(int j=20;j>=0;j--){
        if(jump[a][j]!=jump[b][j]){
            curr += dist[a][j];
            curr += dist[b][j];
            a = jump[a][j];
            b = jump[b][j];
        }
    }
    curr += jump[a][0]+jump[b][0];
    return jump[a][0];
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n;
    for(int i=1;i<=n-1;i++){
        int a,b,c;
        cin >> a >> b >> c;
        roads[a].push_back({b,c});
        roads[b].push_back({a,c});
    }
    dfs(0,-1);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            jump[i][j] = jump[jump[i][j-1]][j-1];
            dist[i][j] = dist[i][j-1]+dist[jump[i][j-1]][j-1];
        }
    }
    cin >> q;
    for(int i=1;i<=q;i++){
        int a,b,c,d,e,ans=0;
        cin >> a >> b >> c >> d >> e;
        set<int> s = {a,b,c,d,e};
        while(s.size()>1){
            vector<vector<int>> v;
            for(int j:s){
                for(int k:s){
                    if(j==k){
                        continue;
                    }
                    int p = lca(j,k);
                    v.push_back({dep[p],curr,p,j,k});
                }
            }
            sort(v.begin(),v.end(),greater<vector<int>>());
            s.erase(v[0][3]);
            s.erase(v[0][4]);
            ans += v[0][1];
            s.insert(v[0][2]);
        }
        cout << ans << "\n";
    }
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1504 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 260 ms 29312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 25448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1504 KB Output is correct
2 Incorrect 260 ms 29312 KB Output isn't correct
3 Halted 0 ms 0 KB -