Submission #245367

#	Time	Username	Problem	Language	Result	Execution time	Memory
245367		karma	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	555 ms	75508 KiB

diameter

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = (int)2e5 + 2;
const ll inf = (ll)1e18;
typedef pair<int, int> pii;

ll lst, W, d[N], lz[N << 2];
struct TEdge {int u, v; ll w;} e[N];
int n, q, in[N], out[N], rv[N * 2], l[N << 2], h[N << 2], Time = 0;
vector<pii> adj[N];
vector<pair<int, ll>> path;

struct TNode { /// x + y - 2 * z
    ll xz, zx, x, z, res;
    int type;
    TNode() {zx = xz = x = z = res = -inf; type = 1;}
    void modify() {
        if(zx < -inf) zx = -inf;
        if(xz < -inf) xz = -inf;
        if(x < -inf) x = -inf;
        if(z < -inf) z = -inf;
        if(res < -inf) res = -inf;
    }
    void update(ll v) {
        x += v, z -= v * 2;
        xz -= v, zx -= v;
        modify();
    }
} st[N << 2];

ostream& operator << (ostream& cout, TNode& x) {
    cout << x.x << ' ' << x.z << ' ' << x.zx << ' ' << x.xz << ' ' << x.res;
    return cout;
}

void update(int& x, int l, int r) {
    st[x].x = max(st[l].x, st[r].x);
    st[x].z = max(st[l].z, st[r].z);
    st[x].xz = max({st[l].xz, st[r].xz, st[l].x + st[r].z});
    st[x].zx = max({st[l].zx, st[r].zx, st[l].z + st[r].x});
    st[x].res = max({st[l].res, st[r].res, st[l].xz + st[r].x, st[l].x + st[r].zx});
    st[x].modify();
}

void down(int x) {
    if(lz[x] == 0 || l[x] == h[x]) return;
    st[x << 1].update(lz[x]);
    st[x << 1 | 1].update(lz[x]);
    lz[x << 1] += lz[x], lz[x << 1 | 1] += lz[x];
    lz[x] = 0;
}

void build(int x, int low, int high) {
    l[x] = low, h[x] = high;
    if(low == high) {
        st[x].type = path[low].fi;
        if(st[x].type == 1) st[x].x = path[low].se;
        else st[x].z = path[low].se;
        return;
    }
    int mid = (low + high) >> 1;
    build(x << 1, low, mid);
    build(x << 1 | 1, mid + 1, high);
    update(x, x << 1, x << 1 | 1);
    //cout << x << ' ' << low << ' ' << high << ' ';
    //cout << st[x] << '\n';
}

void upd(int x, int low, int high, ll val) {
    down(x);
    if(l[x] > high || h[x] < low) return;
    if(low <= l[x] && h[x] <= high) {
        st[x].update(val);
        lz[x] += val;
        return;
    }
    upd(x << 1, low, high, val);
    upd(x << 1 | 1, low, high, val);
    update(x, x << 1, x << 1 | 1);
}

void dfs(int u, int p) {
    path.pb(1, d[u]);
    in[u] = path.size() - 1;
    for(auto& v: adj[u]) {
        if(v.fi == p) continue;
        if(v.fi == e[v.se].u) swap(e[v.se].u, e[v.se].v);
        d[v.fi] = d[u] + e[v.se].w;
        dfs(v.fi, u);
        path.pb(-2, -2ll * d[u]);
    }
    out[u] = path.size() - 1;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> q >> W;
    for(int i = 0; i < n - 1; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        adj[e[i].u].pb(e[i].v, i);
        adj[e[i].v].pb(e[i].u, i);
    }
    dfs(1, 0);
    build(1, 0, path.size() - 1);
    lst = 0;
    ll i, w;
    while(q --) {
        cin >> i >> w;
        i = (lst + i) % (n - 1);
        w = (w + lst) % W;
        upd(1, in[e[i].v], out[e[i].v], w - e[i].w);
        e[i].w = w, lst = max(st[1].res, st[1].x);
        cout << lst << '\n';
    }
}

Compilation message (stderr)

diameter.cpp: In function 'int32_t main()':
diameter.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".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