Submission #446253

#	Time	Username	Problem	Language	Result	Execution time	Memory
446253		qwerasdfzxcl	Dynamic Diameter (CEOI19_diameter)	C++14	24 / 100	5065 ms	22852 KiB

diameter

#include <bits/stdc++.h>
#define int long long

using namespace std;
struct Edge{
    int s, e, x;
    Edge(){}
    Edge(int _s, int _e, int _x): s(_s), e(_e), x(_x){}
}e[100100];
set<pair<int, int>> adj[100100];
int dist[100100];

void dfs(int s, int pa = -1){
    for (auto &v:adj[s]) if (v.first!=pa){
        dist[v.first] = dist[s]+v.second;
        dfs(v.first, s);
    }
}

signed main(){
    int n, q, w;
    scanf("%lld %lld %lld", &n, &q, &w);
    for (int i=0;i<n-1;i++){
        scanf("%lld %lld %lld", &e[i].s, &e[i].e, &e[i].x);
        adj[e[i].s].insert(make_pair(e[i].e, e[i].x));
        adj[e[i].e].insert(make_pair(e[i].s, e[i].x));
    }

    int last = 0;
    while(q--){
        int x, y;
        scanf("%lld %lld", &x, &y);
        x = (x+last)%(n-1);
        y = (y+last)%w;
        adj[e[x].s].erase(adj[e[x].s].find(make_pair(e[x].e, e[x].x)));
        adj[e[x].e].erase(adj[e[x].e].find(make_pair(e[x].s, e[x].x)));
        adj[e[x].s].insert(make_pair(e[x].e, y));
        adj[e[x].e].insert(make_pair(e[x].s, y));
        e[x].x = y;
        dist[1] = 0;
        dfs(1);
        int idx = max_element(dist+1, dist+n+1) - dist;
        dist[idx] = 0;
        dfs(idx);
        last = *max_element(dist+1, dist+n+1);
        printf("%lld\n", last);
    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%lld %lld %lld", &n, &q, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%lld %lld %lld", &e[i].s, &e[i].e, &e[i].x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%lld %lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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