Submission #1300312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300312		lmaobruh	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	265 ms	181164 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 Hmin, Hmax, Hpre, Hsuf, diam;
    node() {
        Hmin=Hmax=Hpre=Hsuf=diam=0;
    }
    node(ll x, ll y, ll z, ll u, ll v) {
        Hmin=x, Hmax=y, Hpre=z, Hsuf=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].Hmin += x;
    t[p].Hmax += x;
    t[p].Hpre -= x;
    t[p].Hsuf -= x;
    la[p] += x;
}

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

node mer(node x, node y) {
    node z = node();
    z.diam = max({x.diam, y.diam, x.Hpre + y.Hmax, x.Hmax + y.Hsuf});
    z.Hmin = min(x.Hmin, y.Hmin);
    z.Hmax = max(x.Hmax, y.Hmax);
    z.Hpre = max({x.Hpre, y.Hpre, x.Hmax - 2LL*y.Hmin});
    z.Hsuf = max({x.Hsuf, y.Hsuf, -2LL*x.Hmin + y.Hmax});
    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 (tin[v[0]] < tin[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:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen("a.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
diameter.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen("a.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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