Submission #946691

#	Time	Username	Problem	Language	Result	Execution time	Memory
946691		Vladth11	Dynamic Diameter (CEOI19_diameter)	C++14	49 / 100	5037 ms	166420 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 <pii> v[NMAX];
vector <int> children[NMAX];
int n;
pii timp[NMAX * nrbits];
 
struct edge {
    int a, b;
    ll c;
} edges[NMAX];
 
class AINT {
public:
    struct Node {
        ll mx, lazy;
    };
    Node* aint;
    int n;
    void init(int _n) {
        n = _n;
        aint = new Node[4 * (n + 1)];
        for(int i = 0; i < 4 * (n + 1); i++) {
            aint[i].mx = 0;
            aint[i].lazy = 0;
        }
    }
    Node combine(Node a, Node b) {
        Node sol = {0, 0};
        sol.mx = max(a.mx, b.mx);
        return sol;
    }
    void propaga(int node, int st, int dr) {
        if(st != dr) {
            aint[node * 2].lazy += aint[node].lazy;
            aint[node * 2 + 1].lazy += aint[node].lazy;
        }
        aint[node].mx += aint[node].lazy;
        aint[node].lazy = 0;
    }
    void baga(int node, int st, int dr, int a, int b, int val) {
        propaga(node, st, dr);
        if(a <= st && dr <= b) {
            aint[node].lazy += val;
            return;
        }
        int mid = (st + dr) / 2;
        if(a <= mid) {
            baga(node * 2, st, mid, a, b, val);
        }
        if(b > mid) {
            baga(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]);
    }
    ll sol(int node, int st, int dr, int a, int b){
        propaga(node, st, dr);
        if(a <= st && dr <= b){
            return aint[node].mx;
        }
        int mid = (st + dr) / 2;
        ll maxim = 0;
        if(a <= mid)
            maxim = max(maxim, sol(node * 2, st, mid, a, b));
        if(b > mid)
            maxim = max(maxim, sol(node * 2 + 1, mid + 1, dr, a, b));
        return maxim;
    }
    void update(int st, int dr, int val) {
        baga(1, 1, n, st, dr, val);
    }
    ll query(int st, int dr) {
        return sol(1, 1, n, st, dr);
    }
} st[NMAX];
 
int viz[NMAX];
int stamp;
 
struct event {
    int st, dr, unde, subarb;
};
 
vector <event> events[NMAX];
 
multiset <ll> candidates;
multiset <ll> indv[NMAX];
 
int sz[NMAX];
int total;
 
void getsz(int node, int p) {
    sz[node] = 1;
    for(auto x : v[node]) {
        if(x.first == p || viz[x.first]) continue;
        getsz(x.first, node);
        sz[node] += sz[x.first];
    }
    total = sz[node];
}
 
int findCentroid(int node, int p) {
    for(auto x : v[node]) {
        if(x.first == p || viz[x.first]) continue;
        if(sz[x.first] > total / 2)
            return findCentroid(x.first, node);
    }
    return node;
}
 
int unde;
int subarb;
 
void DFS(int node, int p) {
    stamp++;
    if(timp[subarb].first == 0) timp[subarb].first = stamp;
    timp[subarb].second = stamp;
    for(auto x : v[node]) {
        if(x.first == p || viz[x.first]) continue;
        event nou = {stamp + 1, 0, unde, subarb};
        DFS(x.first, node);
        nou.dr = stamp;
        events[x.second].push_back(nou);
    }
}
 
int cnt = 0;
 
void centroid(int node) {
    getsz(node, 0);
    int C = findCentroid(node, 0);
    st[C].init(total);
    viz[C] = 1;
    stamp = 1; /// n-are logica tbh
    unde = C;
    for(auto x : v[C]){
        if(viz[x.first]) continue;
        children[C].push_back(++cnt);
        subarb = cnt;
        event nou = {stamp + 1, 0, unde, subarb};
        DFS(x.first, C);
        nou.dr = stamp;
        events[x.second].push_back(nou);
    }
    for(auto x : v[C]) {
        if(viz[x.first]) continue;
        centroid(x.first);
    }
}
 
ll compute(int i){
    if(indv[i].size() == 0)
        return 0;
    if(indv[i].size() == 1)
        return *indv[i].begin();
    auto it =indv[i].end();
    return (*prev(it) + *prev(prev(it)));
}
 
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, i});
        v[b].push_back({a, i});
        edges[i] = {a, b, c};
    }
    centroid(1);
    for(int a = 1; a < n; a++) {
        for(auto x : events[a]) {
            st[x.unde].update(x.st, x.dr, edges[a].c);
        }
    }
    for(i = 1; i <= n; i++){
        //debug(i);
        for(auto x : children[i]){
            //debug(st[i].query(timp[x].first, timp[x].second));
            indv[i].insert(st[i].query(timp[x].first, timp[x].second));
        }
        candidates.insert(compute(i));
    }
    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++;
        int toAdd = b - edges[a].c;
        edges[a].c = b;
        for(auto x : events[a]) {
            candidates.erase(candidates.find(compute(x.unde)));
            indv[x.unde].erase(indv[x.unde].find(st[x.unde].query(timp[x.subarb].first, timp[x.subarb].second)));
            st[x.unde].update(x.st, x.dr, toAdd);
            indv[x.unde].insert(st[x.unde].query(timp[x.subarb].first, timp[x.subarb].second));
            candidates.insert(compute(x.unde));
        }
        cout << *prev(candidates.end()) << '\n';
        last = *prev(candidates.end());
    }
    return 0;
}

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