Submission #1262491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262491		ivano_bozhinovski	Dynamic Diameter (CEOI19_diameter)	C++20	24 / 100	3064 ms	12020 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define pii pair<int,int>
typedef long long ll;

const int maxn=5e5+5;
const ll INF=1e18;

vector<vector<pii>> adj;
vector<int> w;
int n;

pii dijkstra(int s)
{
    priority_queue<pii> q;
    ll d[n+1];
    for(int i=0;i<=n;i++)d[i]=INF;
    d[s]=0;
    q.push({0,s});
    int v,t;
    bool visited[n+1];
    memset(visited,false,sizeof visited);
    while(!q.empty())
    {
        t=-q.top().first;
        v=q.top().second;
        q.pop();
        if(t!=d[v])continue;
        visited[v]=true;
        for(auto u:adj[v])
        {
            if(visited[u.first])continue;
            ll len=t+w[u.second];
            if(len<d[u.first])
            {
                d[u.first]=len;
                q.push({-len,u.first});
            }
        }
    }
    ll odg=0,idx=-1;
    for(int i=1;i<=n;i++)
    {
        if(d[i]>odg)
        {
            odg=d[i];
            idx=i;
        }
    }
    return {odg,idx};

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    ll W;
    cin>>n>>q>>W;
    w.resize(n+1);
    adj.resize(n+1);
    int a,b,c;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b>>c;
        adj[a].pb({b,i});
        adj[b].pb({a,i});
        w[i]=c;
    }
    ll last=0,d,e;
    if(n>5000||q>5000)
    {
        multiset<int> s;
        for(int i=1;i<=n-1;i++)s.insert(w[i]);
        for(int i=0;i<q;i++)
        {
            cin>>d>>e;
            d=(d+last)%(n-1)+1;
            e=(e+last)%W;
            s.erase(s.find(w[d]));
            s.insert(e);
            ll x=*(--s.end());
            s.erase(s.find(x));
            ll ans=x+(*(--s.end()));
            s.insert(x);
            cout<<ans<<endl;
            last=ans;
            w[d]=e;
        }
    }
    for(int i=0;i<q;i++)
    {
        cin>>d>>e;
        d=(d+last)%(n-1)+1;
        e=(e+last)%W;
        w[d]=e;
        int v=dijkstra(1).second;
        last=dijkstra(v).first;
        cout<<last<<endl;
    }


    return 0;
}

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