Submission #1304915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304915		vtnoo	Dynamic Diameter (CEOI19_diameter)	C++20	42 / 100	5093 ms	20940 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

const int N=100005;
const long long INF=1e18;
vector<pair<int,int>> g[N], adj[N], adj_r[N];
pair<int,int> con[N];
int n;
long long dp[N], dp2[N], ed[N], deg[N];

void dfs(int u){
    pair<long long,int> v1={0,0}, v2={0,0};
    long long s=0;
    for(auto [v,i]:adj[u]){
        dfs(v);
        v1=max(v1, {dp[v]+ed[i], v});
        s=max(s, dp2[v]);
    }
    for(auto [v,i]:adj[u]){
        if(v==v1.second)continue;
        v2=max(v2, {dp[v]+ed[i], v});
    }
    dp[u]=v1.first;
    dp2[u]=max({dp[u], v1.first+v2.first, s});
    return;
}

void dfs2(int u, int p){
    for(auto [v,i]:g[u]){
        if(v==p)continue;
        con[i]={u,v};
        adj[u].push_back({v,i});
        adj_r[v].push_back({u,i});
        dfs2(v,u);
    }
}

void dfs3(int u){
    pair<long long,int> v1={0,0}, v2={0,0};
    long long s=0;
    for(auto [v,i]:adj[u]){
        v1=max(v1, {dp[v]+ed[i], v});
        s=max(s, dp2[v]);
    }
    for(auto [v,i]:adj[u]){
        if(v==v1.second)continue;
        v2=max(v2, {dp[v]+ed[i], v});
    }
    dp[u]=v1.first;
    dp2[u]=max({dp[u], v1.first+v2.first, s});
    for(auto [v,i]:adj_r[u]){
        dfs3(v);
    }
}

int main(){
    int q;
    long long w;
    cin>>n>>q>>w;
    for(int i=0;i<n-1;i++){
        int u,v;
        long long c;
        cin>>u>>v>>c;
        g[u].push_back({v,i});
        g[v].push_back({u,i});
        ed[i]=c;
    }
    dfs2(1,-1);
    dfs(1);
    long long last=0;
    while(q--){
        long long d_, e_;
        cin>>d_>>e_;
        long long d=(d_+last)%(n-1);
        long long e=(e_+last)%w;
        ed[d]=e;
        dfs3(con[d].first);
        cout<<dp2[1]<<endl;
        last=dp2[1];
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27