Submission #1220176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220176		Trumling	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	75 ms	14260 KiB

diameter

//Trumling ©
//Αφόδευε υψηλά και ηγνάντει 
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 998244353
#define all(x) x.begin(),x.end()
vector<vector<pair<ll,ll>>>g;
vector<ll>d;
vector<ll>depth;
ll ans=0;
void dia(int start,int pre)
{
    priority_queue<ll>pq;
    depth[start]=0;

    for(auto x:g[start])
        if(x.F!=pre)
        {
            dia(x.F,start);
            pq.push(depth[x.F]+d[x.S]);
        }

    if(pq.empty())
        depth[start]=0;
    else
        depth[start]=pq.top();
    
    if(pq.size()>=2)
    {
        ll w1=pq.top();
        pq.pop();

    ans=max(ans,w1+pq.top());
    }
    ans=max(ans,depth[start]);
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n,q,w;
cin>>n>>q>>w;
g.assign(n+1,vector<pair<ll,ll>>());
d.assign(n,0);
depth.assign(n,0);

for(int i=0;i<n-1;i++)
{
ll x,y,z;
cin>>x>>y>>z;

g[x].pb({y,i});
g[y].pb({x,i});
d[i]=z;
}
ll last=0;

priority_queue<pair<ll,ll>>pq;
for(int i=0;i<n-1;i++)
    pq.push({d[i],i});

while(q--)
{
    ll x,y;
    cin>>x>>y;
    x=(x+last)%(n-1);
    y=(y+last)%w;

    //cout<<x<<' '<<y<<'\n';
    d[x]=y;
    pq.push({d[x],x});

    pair<ll,ll>w1;
    while(pq.top().F!=d[pq.top().S])
        pq.pop();

    w1=pq.top();
    if(n==2)
    {
    ans=w1.F;
    cout<<ans<<'\n';
    last=ans;
    continue;
    }
    pq.pop();
    while(pq.top().F!=d[pq.top().S])
        pq.pop();


    ans=pq.top().F + w1.F;
    pq.push(w1);
    //dia(1,1);
    cout<<ans<<'\n';
    last=ans;
}

}

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