Submission #1262458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262458		mkkkkkkkk	Dynamic Diameter (CEOI19_diameter)	C++20	24 / 100	945 ms	9644 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;
    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;
    }



    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