Submission #1262470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262470		mkkkkkkkk	Dynamic Diameter (CEOI19_diameter)	C++20	24 / 100	5094 ms	16656 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

vector<pair<long long,long long>> adj[100001];

        long long dist[5001];

        void dfs(long long i,long long d)
        {
            dist[i]=d;
            for(auto it : adj[i])
            {
                long long br=it.first;
                long long br2=it.second;
                if(dist[br]==-1)
                    dfs(it.first,d+br2);
            }
        }

int main()
{

    ios::sync_with_stdio((false));
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,q,w;
    cin>>n>>q>>w;
    if(n<=5000 && q<=5000)
    {
             vector<pair<long long,long long>> edges;
        for(long long n1=n-1;n1>0;n1--)
        {
            long long a,b,c;
            cin>>a>>b>>c;
            edges.push_back({a,b});
            adj[a].push_back({b,c});
            adj[b].push_back({a,c});
        }
        long long last=0;
        for(;q>0;q--)
        {
            long long d,e;
            cin>>d>>e;
            d=(d+last)%(n-1);
            e=(e+last)%w;
            pair<long long,long long> par=edges[d];
            for(long long i=0;i<adj[par.first].size();i++)
            {
                if(adj[par.first][i].first==par.second)
                {
                    adj[par.first][i].second=e;
                }

            }
            for(long long i=0;i<adj[par.second].size();i++)
            {
                if(adj[par.second][i].first==par.first)
                {
                    adj[par.second][i].second=e;
                }

            }
            memset(dist,-1,sizeof(dist));
            dfs(1,0);
            pair<long long,long long> maxx={0,0};
            for(long long i=1;i<=n;i++)
            {
                maxx=max(maxx,{dist[i],i});
            }
            long long br=maxx.second;

            memset(dist,-1,sizeof(dist));
            dfs(br,0);
            pair<long long,long long> maxx2={0,0};
            for(long long i=1;i<=n;i++)
            {
                maxx2=max(maxx2,{dist[i],i});
            }
            last=maxx2.first;
            cout<<last<<endl;
        }
    }
    else
    {
        long long arr[n]={};
        vector<pair<long long,long long>> edges;
        set<pair<long long,long long>> st;
        for(long long i=0;i<n-1;i++)
        {
            long long a,b,c;
            cin>>a>>b>>c;
            edges.push_back({a,b});
            adj[a].push_back({b,c});
            adj[b].push_back({a,c});
            arr[i]=c;
            st.insert({-c,i});
        }
        long long last=0;
        for(;q>0;q--)
        {
            long long d,e;
            cin>>d>>e;
            d=(d+last)%(n-1);
            e=(e+last)%w;
            st.erase({-arr[d],d});
            arr[d]=e;
            st.insert({-e,d});
            long long br=2;
            long long res=0;
            for(auto it : st)
            {
                res-=it.first;
            }
            cout<<res<<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