Submission #1300262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300262		lmaobruh	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	274 ms	175132 KiB

diameter

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

#define ll long long
#define ii pair<int, int>
#define fi first
#define se second
#define fo(i,a,b) for (int i = (a); i <= (b); ++i)
#define fd(i,a,b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define maxi(a,b) a=max(a,b)
#define mini(a,b) a=min(a,b)
#define ve vector
#define pb push_back
#define er(x) cerr << (#x) << " = " << x << '\n'
#define _ << ' ' <<
#define sus siuuuuu

const int N = 1e6+5, inf = 1e9+10, mod = 1e9+7;

/**



**/

struct node {
    ll Lmin, Lmax, Rmin, Rmax, diam;
    node() {
        Lmin=Lmax=Rmin=Rmax=diam=0;
    }
    node(ll x, ll y, ll z, ll u, ll v) {
        Lmin=x, Lmax=y, Rmin=x, Rmax=u, diam=v;
    }
} t[N<<2];

ll la[N<<2];

#define lc (p<<1)
#define rc (lc|1)

void write(int p, ll x) {
    t[p].Lmin += x;
    t[p].Lmax += x;
    t[p].Rmin += x;
    t[p].Rmax += x;
    la[p] += x;
}

void down(int p) {
    if (la[p]) {
        write(lc, la[p]);
        write(rc, la[p]);
        la[p] = 0;
    }
}

/// Lmax, Lmin, Rmin, Rmax
/// max, min,   min, max

node mer(node x, node y) {
    node z = node();
    z.diam = max(x.diam, y.diam);
    maxi(z.diam, x.Lmax + max(y.Lmax, y.Rmax) - 2*x.Lmin);
    maxi(z.diam, max(x.Lmax, x.Rmax) + y.Rmax - 2*y.Rmin);
    z.Lmax = x.Lmax;
    z.Lmin = x.Lmin;
    if (y.Lmin < z.Lmin || y.Lmax - y.Lmin > z.Lmax - z.Lmin) {
        z.Lmin = y.Lmin;
        maxi(z.Lmax, y.Lmax);
    }
    z.Rmax = y.Rmax;
    z.Rmin = y.Rmin;
    if (x.Rmin < z.Rmin || x.Rmax - x.Rmin > z.Rmax - z.Rmin) {
        z.Rmin = x.Rmin;
        maxi(z.Rmax, x.Rmax);
    }
    return z;
}

void add(int p, int l, int r, int u, int v, ll x) {
    if (l>v||r<u) return;
    if (u<=l&&r<=v) return write(p, x);
    int mid = (l + r) / 2; down(p);
    add(lc, l, mid, u, v, x);
    add(rc, mid+1, r, u, v, x);
    t[p] = mer(t[lc], t[rc]);
}

int n, q, tin[N], tout[N], tour[N], tim;
ll tmp, sum[N];
ve<pair<int, ll>> g[N];

void dfs(int u, int p = -1) {
    tim++; tin[u]=tim, tour[tim]=u;
    for (auto &x:g[u]) if (x.fi != p) {
        sum[x.fi]=sum[u]+x.se;
        dfs(x.fi, u);
        tour[++tim]=u;
    }
    tout[u]=tim;
}

void init(int p, int l, int r) {
    if (l == r) {
        int x=tour[l];
        t[p] = node{sum[x],sum[x],sum[x],sum[x],0};
        return;
    }
    int mid = (l + r) / 2;
    init(lc, l, mid);
    init(rc, mid+1, r);
    t[p]=mer(t[lc],t[rc]);
}

ve<array<ll,3>> eds;

void solve() {
    cin >> n >> q >> tmp;
    fo(i,1,n-1) {
        ll u, v, c;
        cin >> u >> v >> c;
        g[u].pb({v,c});
        g[v].pb({u,c});
        eds.pb({u,v,c});
    }
    dfs(1);
    int m = 2*n-1;
    for (auto &v : eds) {
        if (sum[v[0]] < sum[v[1]]) swap(v[0],v[1]);
    }
    init(1,1,m);
    ll last = 0;
    while (q--) {
        ll d, e; cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % tmp;
        add(1,1,m,tin[eds[d][0]],tout[eds[d][0]],e-eds[d][2]);
        eds[d][2]=e;
        last = t[1].diam;
        cout << last << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    if (fopen("a.inp","r")) {
        freopen("a.inp","r",stdin);
        freopen("a.out","w",stdout);
    }

    solve();
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen("a.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
diameter.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen("a.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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