Submission #1104744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104744		SSSM	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	5060 ms	10480 KiB

diameter

#include <bits/stdc++.h>

/*
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
*/

using namespace std;

/*
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define F first
#define S second
#define pb push_back
#define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
#define md(a) (a%mod+mod)%mod
#define all(a) a.begin(), a.end()
#define MP make_pair
#define lc id<<1
#define rc lc|1
#define mid (l+r)/2
#define kill(a) cout << a << "\n", exit(0)
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
mt19937_64  rng(chrono::steady_clock::now().time_since_epoch().count());

ll const maxn=1e5+10, mod=1e9+7, INF=1e18, LOG=45, sq=65;

ll poww(ll a, ll b, ll mod) {
 if (b == 0) return 1;
 return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod;
}

ll n, q, w, W[maxn], mx, dis[maxn], dp[maxn];
vector<pll> g[maxn];

void DFS(ll v, ll p=0)
{
    vector<pll> vec;
    for(auto [u, id]:g[v])
    {
        if(u!=p)
        {
            DFS(u, v);
            vec.pb({dp[u], id});
        }
    }

    for(auto [i, id]:vec)
    {
        dp[v]=max(dp[v], i+W[id]);
    }
}

int main() 
{ 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    cin>>n>>q>>w;
    for(ll i=1;i<n;i++)
    {
        ll v, u, w;
        cin>>v>>u>>w;
        g[v].pb({u, i});
        g[u].pb({v, i});
        W[i]=w;
    }

    ll last=0;
    while(q--)
    {
        ll d, e;
        cin>>d>>e;
        d=(d+last)%(n-1);
        e=(e+last)%w;
        W[d+1]=e;
        fill(dp, dp+n+1, 0);
        DFS(1);
        ll mx=-INF, mx2=-INF;
        for(auto [u, id]:g[1])
        {
            if(dp[u]+W[id]>mx)
            {
                mx=dp[u]+W[id];
                mx2=mx;
            }
            else if(dp[u]+W[id]>mx2)
            {
                mx2=dp[u]+W[id];
            }
        }
        if(g[1].size()==1)
        {
            cout<<dp[1]<<"\n";
            last=dp[1];
        }
        else{
            cout<<mx+mx2<<"\n";
            last=mx+mx2;
        }
    }

    return 0;


}

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