Submission #1245449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245449		abdelhakim	Dynamic Diameter (CEOI19_diameter)	C++20	7 / 100	602 ms	29840 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);
}
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);
  multiset<ll> st;
  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;
    st.insert(c);
  }
  ll last=0;
  while(q--)
  {
    ll d,e;
    cin>>d>>e;
    d=(d+last)%(n-1);
    e=(e+last)%w;
    auto it=st.find(wt[edges[d]]);
    st.erase(it);
    wt[edges[d]]=e;
    wt[{edges[d].second,edges[d].first}]=e;
    st.insert(e);
    // dfs(0,0);
    // cout << diameter[0] << endl;
    ll ans=*st.rbegin();
    if(st.size() > 1) ans+=*(++st.rbegin());
    last=ans;
    cout << ans << endl;
  }
}

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