Submission #945068

#	Time	Username	Problem	Language	Result	Execution time	Memory
945068		Vladth11	Dynamic Diameter (CEOI19_diameter)	C++14	11 / 100	5040 ms	39972 KiB

diameter

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 100002;
const ll INF = (1LL << 58);
const ll nrbits = 18;
const ll MOD = 998244353;

vector <int> v[NMAX];
pii diameter;
ll lung;
int dp[nrbits + 1][NMAX];
ll lazy[NMAX * 4];
pii aint[NMAX * 4];
pii timp[NMAX];
int stamp;
int n;

void propaga(int node, int st, int dr) {
    if(st != dr) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    aint[node].first += lazy[node];
    lazy[node] = 0;
}

pii combine(pii a, pii b) {
    return max(a, b);
}

void update(int node, int st, int dr, int a, int b, ll val) {
    propaga(node, st, dr);
    if(a <= st && dr <= b) {
        lazy[node] += val;
        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid)
        update(node * 2, st, mid, a, b, val);
    if(b > mid)
        update(node * 2 + 1, mid + 1, dr, a, b, val);
    propaga(node * 2, st, mid);
    propaga(node * 2 + 1, mid + 1, dr);
    aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}

pii query(int node, int st, int dr, int a, int b) {
    propaga(node, st, dr);
    if(a <= st && dr <= b) {
        return aint[node];
    }
    int mid = (st + dr) / 2;
    pii sol = {0, 0};
    if(a <= mid) {
        sol = combine(sol, query(node * 2, st, mid, a, b));
    }
    if(b > mid) {
        sol = combine(sol, query(node * 2 + 1, mid + 1, dr, a, b));
    }
    return sol;
}

struct edge {
    int a, b;
    ll c;
} edges[NMAX];

int preorder[NMAX];

void build(int node, int st, int dr) {
    if(st == dr) {
        aint[node].second = preorder[st];
        return;
    }
    int mid = (st + dr) / 2;
    build(node * 2, st, mid);
    build(node * 2 + 1, mid + 1, dr);
}

void DFS(int node, int p) {
    timp[node].first = ++stamp;
    preorder[stamp] = node;
    dp[0][node] = p;
    for(auto x : v[node]) {
        if(x == p) continue;
        DFS(x, node);
    }
    timp[node].second = stamp;
}

bool isParent(int a, int b) {
    return timp[a].first <= timp[b].first && timp[b].second <= timp[a].second;
}

int LCA(int a, int b) {
    int r = b, pas = nrbits;
    while(pas >= 0) {
        int nxt = dp[pas][r];
        if(nxt != 0 && !isParent(nxt, a)) {
            r = nxt;
        }
        pas--;
    }
    if(!isParent(r, a)) {
        r = dp[0][r];
    }
    return r;
}

ll lgt(int a, int b) {
    int lca = LCA(a, b);
    return query(1, 1, n, timp[a].first, timp[a].first).first + query(1, 1, n, timp[b].first, timp[b].first).first - 2 * query(1, 1, n, timp[lca].first, timp[lca].first).first;
}

void extend(int i) {
    pii initial = diameter;
    // debugs(i);
    int prim = lgt(diameter.first, i);
    int sec = lgt(diameter.second, i);
    //debugs(prim);
    //  debug(sec);
    if(lung < prim) {
        lung = prim;
        diameter = {initial.first, i};
    }
    if(lung < sec) {
        lung = sec;
        diameter = {initial.second, i};
    }
}

int main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int q, w, i;
    cin >> n >> q >> w;
    for(i = 1; i < n; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        v[a].push_back(b);
        v[b].push_back(a);
        edges[i] = {a, b, c};
    }
    DFS(1, 0);
    for(int j = 1; j <= nrbits; j++) {
        for(i = 1; i <= n; i++) {
            dp[j][i] = dp[j - 1][dp[j - 1][i]];
        }
    }
    build(1, 1, n);
    for(i = 1; i < n; i++) {
        if(dp[0][edges[i].a] == edges[i].b) {
            swap(edges[i].a, edges[i].b);
        }
        update(1, 1, n, timp[edges[i].b].first, timp[edges[i].b].second, edges[i].c);
    }
    diameter = {1, 2};
    lung = lgt(1, 2);
    for(int j = 1; j <= n; j++) {
        extend(j);
    }
    ll last = 0;
    for(i = 1; i <= q; i++) {
        ll a, b;
        cin >> a >> b;
        a += last;
        a %= (n - 1);
        b += last;
        b %= w;
        a++;
        update(1, 1, n, timp[edges[a].b].first, timp[edges[a].b].second, b - edges[a].c);
        edges[a].c = b;
        lung = lgt(diameter.first, diameter.second);
         for(int j = 1; j <= n; j++) {
        extend(j);
    }
        last = lung;
        cout << lung << "\n";
    }
    return 0;
}

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