Submission #1245454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245454		abdelhakim	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	5089 ms	24080 KiB

diameter

#include <bits/stdc++.h>
#define ll long long
#define inf (ll)(1e15) 
#define mod (ll)1e9+7
#define dbg(x) cerr <<#x << ' ' << x <<endl;
using namespace std;

void printvec(vector<ll>& v)
{
  for (auto &&i : v)
  {
    cout <<i<<' ';
  }
  cout << endl;
}

vector<pair<ll,ll>> dp;
map<pair<ll,ll>,ll> wt;
vector<vector<ll>> adj;
vector<ll> parr;
vector<ll> diameter;
void dfs(ll node, ll par)
{
  parr[node]=par;
  ll mx1=0;
  ll mx2=0;
  ll mxd=0;
  for (auto &&e : adj[node])
  {
    if(e==par)continue;
    dfs(e,node);
    ll v=wt[{node,e}]+dp[e].second;
    mxd=max(mxd,diameter[e]);
    if(v > mx2)
    {
      mx2=v;
      if(mx2>mx1) swap(mx1,mx2);
    }
  }
  dp[node]={mx1+mx2,mx1};
  diameter[node]=max(mxd,dp[node].first);
}
void tl3(ll node)
{
  if(node==0) return;
  ll mx1=0;
  ll mx2=0;
  ll mxd=0;
  for (auto &&e : adj[node])
  {
    if(e==parr[node]) continue;
    ll v=wt[{node,e}]+dp[e].second;
    mxd=max(mxd,diameter[e]);
    if(v > mx2)
    {
      mx2=v;
      if(mx2>mx1) swap(mx1,mx2);
    }
  }
  dp[node]={mx1+mx2,mx1};
  diameter[node]=max(mxd,dp[node].first);
  tl3(parr[node]);
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n,q,w;
  cin>>n>>q>>w;
  vector<pair<ll,ll>> edges(n-1);
  adj.resize(n);
  dp.resize(n);
  parr.resize(n);
  diameter.resize(n);
  for (int i=0;i<n-1;i++)
  {
    ll c;
    cin>>edges[i].first>>edges[i].second>>c;
    edges[i].first--;
    edges[i].second--;
    adj[edges[i].first].push_back(edges[i].second);
    adj[edges[i].second].push_back(edges[i].first);
    ll u=edges[i].first;
    ll v=edges[i].second;
    wt[{u,v}]=c;
    wt[{v,u}]=c;
  }
  dfs(0,0);
  ll last=0;
  while(q--)
  {
    ll d,e;
    cin>>d>>e;
    d=(d+last)%(n-1);
    e=(e+last)%w;
    wt[edges[d]]=e;
    wt[{edges[d].second,edges[d].first}]=e;
    ll nd=edges[d].second;
    if(edges[d].second == parr[edges[d].first]) nd=edges[d].first;
    tl3(nd);
    cout << diameter[0] << endl;
    last=diameter[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