Submission #1242307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242307		yassia	Dynamic Diameter (CEOI19_diameter)	C++20	24 / 100	5093 ms	15120 KiB

diameter

#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
#define int ll
using pii = pair<int, int>;
using pll = pair<ll,ll>;
using str = string;
using ld = long double;
using hash_map =gp_hash_table<int, int>;
using hash_set= gp_hash_table <int, null_type>;
auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);
typedef tree<ll, null_type, less<>, rb_tree_tag,
        tree_order_statistics_node_update> ord_set;
const ll maxn = 3e5+8;
const ll inf = 2e18+7;
ll n;
ll dist[maxn];
ll d_bfs[maxn];
ll pr[maxn];
ll wei[maxn];
void cntp(ll v, vector<vector<ll>>&g,ll p){
    pr[v] = p;
    for (auto u: g[v]) {
        if (u != p){
            cntp(u, g, v);
        }
    }
}
void dfs(ll v, vector<vector<ll>>&g){
    if (pr[v]!=-1)dist[v] = dist[pr[v]] +wei[v];
    else dist[v] = 0;
    for (auto u : g[v]){
        if (u != pr[v]){
            dfs(u, g);
        }
    }
}
void bfs(ll u, vector<vector<ll>> &g){
    for(int i = 1; i <= n; i++){
        d_bfs[i] = inf;
    }
    d_bfs[u] = 0;
    queue<ll> q;
    q.push(u);
    ll w=  0;
    while (!q.empty()){
        u= q.front();
        q.pop();
        for (auto v  : g[u]){
            if (pr[u]==v) w = wei[u];
            else w = wei[v];
            if (d_bfs[v]>d_bfs[u]+w){
                d_bfs[v]= d_bfs[u]+w;
                q.push(v);
            }
        }
    }
}
void solve1() {
    ll  q, ww;
    cin >> n >> q>>ww;
    vector<vector<ll>> g(n+1);
    // 3 and 5g
    // 1 and 2
    // 4
    vector<vector<ll>>edges;
    for (int i =0; i < n-1; i++){
        ll u, v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        ll w; cin >> w;
        edges.push_back({u, v, w});
    }
    ll root = 1;
    for (int i = 1; i <= n; i++){
        if (g[i].size()>=2){
            root = i;
            break;
        }
    }cntp(root, g, -1);
    for (auto t : edges){
        ll u = t[0]; ll v = t[1];
        ll w = t[2];
        if (pr[u]==v){
            wei[u] = w;
        }
        else wei[v] = w;
    }
    if (n <= 100000){
        ll last= 0;
        for (int j =0 ; j < q; j++){
            ll dj, ej;
            cin>>dj>>ej;
            dj = (dj+last)%(n-1);
            ej = (ej+last)%ww;
            edges[dj][2] = ej;
            if (edges[dj][0] == pr[edges[dj][1]]){
                wei[edges[dj][1]] = ej;
            }
            else {
                wei[edges[dj][0]] = ej;
            }
            dfs(root, g);
            ll u1 =root;
            ll w1 = 0;
            for (int i = 1; i<= n;i++){
                if (dist[i]>w1){
                    w1 = dist[i];
                    u1= i;
                }
            }
            bfs(u1, g);
            ll mx_ans = 0;
            for (int i = 1; i <= n; i++){
                mx_ans =max(mx_ans, d_bfs[i]);
            }
            last = mx_ans;
            cout<<mx_ans<<endl;
        }
    }
   // else if ()
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t1 = 1;
    while (t1) solve1(), t1--;

#ifdef local
    printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC);
#endif
}

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