Submission #1108526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108526		crafticat	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	5081 ms	488656 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using ll = long long;
template<typename T>
using V = vector<T>;
using vi = V<ll>;
using vb = V<bool>;
using pi = pair<ll,ll>;

#define F0R(i,n) for (ll i = 0; i < n;i++)
#define FOR(i, j, n) for(ll i = j; i < n;i++)
#define ckmin(x,y) x = min(x,y)
#define f first
#define s second
#define pb push_back
#define sor(a,b) min(a,b), max(a,b)
const pi emp = {0, 0};

V<V<ll>> g;

vb vis;
vi siz;

void calcSize(ll x, ll p) {
    siz[x] = 1;

    for (auto y : g[x]) {
        if (y == p || vis[y]) continue;

        calcSize(y, x);
        siz[x] += siz[y];
    }
}

ll find_cen(ll x, ll p, ll N) {
    for (auto y : g[x]) {
        if (y == p || vis[y]) continue;

        if (siz[y] * 2 > N)
            return find_cen(y,x,N);
    }

    return x;
}

struct Seg {
    Seg *left = nullptr, *right = nullptr;
    ll l, r, mid;
    pi v;
    ll lazy = 0;

    Seg(ll l, ll r, vi &ind) : l(l), r(r), mid((r + l) / 2) {
        if (r - l > 1) {
            left = new Seg(l,mid, ind);
            right = new Seg(mid, r, ind);

        } else
            v = {0,ind[l]};
    }
    void push() {
        if (lazy == 0) return;
        v.f += lazy;
        if (r -l > 1) {
            left->lazy += lazy;
            right->lazy += lazy;
        }
        lazy = 0;
    }

    void update(ll a, ll b, ll u) {
        push();

        if (b <= l || a >= r) return;
        if (a <= l && b >= r) {
            lazy += u;
            push();
            return;
        }
        left->update(a,b, u);
        right->update(a,b,u);
        v = max(left->v, right->v);
    }
    pi q(ll a, ll b) {
        push();

        if (b <= l || a >= r) return emp;
        if (a <= l && b >= r) return v;
        return max(left->q(a,b), right->q(a,b));
    }
};

struct Cent {
    vi child;
    unordered_map<ll, ll> in_order, out_order;
    unordered_map<ll,ll> mainSubTree;
    Seg* seg;
    Cent *par = nullptr;

    Cent(ll x) {
        ll t = 0;
        dfs(x, -1, t);
        seg = new Seg(0, in_order.size(), child);
    }

    void dfs(ll x, ll p, ll &t, ll subTree = -1) {
        in_order[x] = t++;
        child.pb(x);
        mainSubTree[x] = subTree;

        for (auto y : g[x]) {
            if (y == p || vis[y]) continue;
            dfs(y,x, t,subTree == -1 ? y : subTree);
        }
        out_order[x] = t;
    }

    void update(ll a, ll p, ll u) {
        if (in_order[a] < in_order[p]) swap(a,p);
        seg->update(in_order[a], out_order[a], u);

        if (par) par->update(a,p,u);
    }

    pi q(ll node) {
        // Get a subtree
        ll in_order_node = in_order[node];
        ll sub = mainSubTree[node];
        ll distanceToCen = seg->q(in_order_node, in_order_node + 1).f;
        pi distance = max(seg->q(0, in_order[sub]), seg->q(out_order[sub],in_order.size()));

        distance.f += distanceToCen;
        return max(distance, par ? par->q(node) : emp);
    }
};

V<Cent*> centroids;
vi centroidDepth;

Cent* cent_decomp(ll x, ll d = 0) {
    calcSize(x, -1);
    ll cen = find_cen(x, -1, siz[x]);

    centroids[cen] = new Cent(cen);
    centroidDepth[cen] = d;
    vis[cen] = true;

    for (auto y : g[cen]) {
        if (vis[y]) continue;
        cent_decomp(y, d + 1)->par = centroids[cen];
    }
    return centroids[cen];
}

map<pi, ll> weights;

void updateWeight(ll a, ll b, ll newW) {
    if (a > b) swap(a,b);
    ll diff = newW - weights[{a,b}];
    ll centPar = a, centChild = b;
    if (centroidDepth[centPar] > centroidDepth[centChild]) swap(centPar, centChild);
    centroids[centPar]->update(centChild, centPar, diff);

    weights[{a,b}] = newW;
}

pi queryFar(ll x) {
    return centroids[x]->q(x);
}

// 278
int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    ll cMAX;
    ll n, q; cin >> n >> q >> cMAX;
    g.resize(n + 1);

    V<pi> edges(n);
    V<ll> initC(n);

    F0R(i, n - 1) {
        ll a, b, c; cin >> a >> b >> c;
        g[a].pb(b);
        g[b].pb(a);
        edges[i] = {a,b};
        initC[i] = c;
    }

    centroids.resize(n + 1);
    centroidDepth.resize(n + 1);
    vis.resize(n + 1);
    siz.resize(n + 1);
    cent_decomp(1);

    F0R(i, n - 1)
        updateWeight(edges[i].f, edges[i].s, initC[i]);

    ll last = 0;

    F0R(i, q) {
        ll e;
        ll c; cin >> e >> c;
        e = (e + last) % (n - 1);
        c = (last + c) % (cMAX);

        auto [a,b] = edges[e];
        updateWeight(a, b, c);
        ll f1 = queryFar(1).s;
        ll results = queryFar(f1).f;

        cout << results << "\n";
        last = results;
    }

    return 0;
}

Compilation message (stderr)

diameter.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
diameter.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

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