oj.uz

Submission #626948

# Submission time Handle Problem Language Result Execution time Memory
626948 2022-08-12T02:39:08 Z Glory Paths (RMI21_paths) C++17
12 / 100
 374 ms 22172 KB 
#include<bits/stdc++.h>
using namespace std;
int n,k,res=0,l[100005];
long long d[100005];
int parent[100005];
int sparse_table[100005][25];
vector<pair<int,int>> gr[100005];
pair<long long,int> a;
 
void dfs(int u,int par,long long dh,int lh) {
    parent[u]=par;
    sparse_table[u][0] = par;
    l[u] = lh;
    d[u] = dh;
    for (auto [v,w]: gr[u]){
        if(v != par){
            dfs(v,u,w+dh,lh+1);
        }
    }
}
 
void dfs_1(int u,int par,long long dh) {
    a = max(a, {dh,u});
    for(auto [v,w]: gr[u]){
        if(v != par){
            dfs_1(v, u, w+dh);
        }
    }
}

void preprocess_lca() {
    
 
    for (int k = 1; k <= 20; k++){
        for (int i = 1; i <= n; i++){
            sparse_table[i][k] = sparse_table[sparse_table[i][k - 1]][k - 1];
        }
    }
}
 
int lca(int p, int q) {
    
    for (int i = 20; i >= 0; i--){
        if (l[sparse_table[p][i]] >= l[q]){
            p = sparse_table[p][i];
        }
    }
    for (int i = 20; i >= 0; i--){
        if (l[sparse_table[q][i]] >= l[p]){
            q = sparse_table[q][i];
        }
    }
 
    if (p == q){
        return p;
    }
    
    for (int i = 20; i >= 0; i--){
        if (sparse_table[p][i] != sparse_table[q][i]) {
            p = sparse_table[p][i];
            q = sparse_table[q][i];
        }
    }
    return parent[p];
}

int32_t main(){
    cin>>n>>k;
    for(int i = 1;i < n; i++){
        int u,v,w;
        cin>>u>>v>>w;
        gr[u].push_back({v,w});
        gr[v].push_back({u,w});
    }
    
    
    a = {-100,-100};
    dfs_1(1,-1,0);
    int pa = a.second;
    
    a = {-100,-100};
    dfs_1(pa,-1,0);
    int pb = a.second;
    
    
    dfs(1,-1,0ll,0);
    preprocess_lca();
    
    for(int i = 1;i <= n; i++){
       cout<<max(d[i]+d[pa]-d[lca(i,pa)]*2, d[i]+d[pb]-d[lca(i,pb)]*2)<<endl;
    }
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 18776 KB Output is correct
2 Correct 369 ms 22172 KB Output is correct
3 Correct 358 ms 20560 KB Output is correct
4 Correct 320 ms 20924 KB Output is correct
5 Correct 360 ms 21776 KB Output is correct
6 Correct 374 ms 20880 KB Output is correct

Subtask #6
0 / 32.0

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