Submission #626936

#	Time	Username	Problem	Language	Result	Execution time	Memory
626936		Glory	Paths (RMI21_paths)	C++17	0 / 100	353 ms	30840 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,res=0,l[100005],parent[100005], passed[100005];
int sparse_table[100005][25];
vector<pair<int,int>> gr[100005];
pair<int,int> a;
 
void dfs(int u){
    for (auto [v,w] : gr[u]){
        if(parent[v] == 0){
            parent[v] = u;
            l[v] = l[u] + w;
            dfs(v);
        }
    }
}

void dfs_1(int u,int d){
    a = max(a, make_pair(d,u));
    for(auto [v,w] : gr[u]){
        if (!passed[v]){
            passed[v] = 1;
            dfs_1(v, w+d);
        }
    }
}


void preprocess_lca() {
    for (int i = 1; i <= n; i++){
        sparse_table[i][0] = parent[i];
    }
 
    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});
    }
    
    memset(passed,0,sizeof(passed));
    memset(parent,0,sizeof(parent));
    
    a = {-100,-100};
    dfs_1(1,0);
    int pa = a.second;
    
    memset(passed,0,sizeof(passed));
    
    a = {-100,-100};
    dfs_1(pa,0);
    int pb = a.second;
    
    
    dfs(1);
    preprocess_lca();
    
    for(int i = 1;i <= n; i++){
       cout<<max(l[i]+l[pa]-l[lca(i,pa)]*2, l[i]+l[pb]-l[lca(i,pb)]*2)<<endl;
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32