제출 #872819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872819		bobbilyking	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	5013 ms	32784 KiB

diameter

// annoying impl i dont want to deal with rn

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

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)

#define NN 100010
#define M 1000000007 // 998244353

vector<pl> adj[NN];

ll belong[NN], w[NN]; // maps original edge -> which edge it belongs to now

ll down[NN], par[NN]; // in the new tree, the node below edge I = down[i], and parent of node X in new tree
ll parEdge[NN]; // wehn traversing par, what is the edge I use
ll curw[NN]; // current weight of edge 

ll edgeidx = 0; 

void dfs(ll i, ll p, ll vpar) {
    ll children = 0;
    for (auto [x, _]: adj[i]) if (x-p) children++;
    if (children == 1) {
        for (auto [x, eidx]: adj[i]) if (x-p) {
            belong[eidx] = edgeidx;
            dfs(x, i, vpar);
        }
    } else {
        if (i != p) {
            down[edgeidx] = i;
            par[i] = vpar;
            parEdge[i] = edgeidx;
            edgeidx++;
        }
        for (auto [x, eidx]: adj[i]) if (x-p) {
            belong[eidx] = edgeidx;
            dfs(x, i, i);
        }
    }
}

struct my_multiset {
    map<ll, ll> cont; // underlying container
    ll sz = 0;

    void insert(ll v) {
        cont[v]++;
        ++sz;
    }
    void erase(ll v) {
        if (!--cont[v]) cont.erase(v); 
        --sz;
    }
    ll size() const {
        return sz;
    }

    ll maximum() const {
        return cont.rbegin()->K;
    }
    ll max2() const {
        assert(sz>=2);
        if (cont.rbegin()->V >= 2) return cont.rbegin()->K*2;
        return cont.rbegin()->K + (*++cont.rbegin()).K;
    }
};

my_multiset all_answer; // all subtree answers
ll curans[NN]; //current answer

my_multiset childrenPull[NN]; // the curD's of my children

vector<pl> children[NN]; // children -> curD

ll ROOT(ll i) {
    return par[i] == i || par[i] == -1;
}

ll getOneEdge(ll i) { // CANNOT be 1
    if (childrenPull[i].size() == 0) return 0;
    return childrenPull[i].maximum(); 
}

void recompute(ll i, ll modified, ll iterations=0) {
    // cout << "asking to recompute " << i << " with child " << modified << " modified " << endl; 
    // cout << "lol " << i << " " << modified << endl;
    // recomptues maximal down

    // cout << "LOL " << childrenPull[i].size() << ": ";
    // for (auto x: childrenPull[i]) cout << x << " , "; cout << endl;

    auto it = lower_bound(A(children[i]), pl{modified, -1}); 

    childrenPull[i].erase(it->V);
    it->V = curw[parEdge[modified]] + getOneEdge(modified);
    childrenPull[i].insert(it->V);

    all_answer.erase(curans[i]);

    if (childrenPull[i].size() <= 1) 
        curans[i] = 0;
    else {
        // cout << "YA " << childrenPull[i].maximum() << ", " << childrenPull[i].max2() << " for " << i << " " << modified << endl;
        curans[i] = childrenPull[i].max2();
    }

    all_answer.insert(curans[i]);

    assert(iterations <= 20);
    if (!ROOT(i)) recompute(par[i], i, iterations++);
}

int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    G(n) G(q) G(W)
    memset(par, -1, sizeof par);
    vector<ll> weights(n-1);
    F(i, 0, n-1) {
        G(x) G(y) cin >> weights[i];
        adj[x].emplace_back(y, i);
        adj[y].emplace_back(x, i);
    }


    // We want to dfs from a non-leaf root node.
    // Unless n=2; then it's trivial.

    if (n==2) {
        ll last = 0;
        while (q--) {
            G(d) G(e)
            d = (d + last)%(n-1);
            e = (e + last)%W;
            last = e;
            cout << last << '\n';
        }
        exit(0);    
    }


    F(root, 1, n+1) if (adj[root].size() >1) {
        dfs(root, -1, root); break;
    }

    F(i, 1, n+1) if (~par[i]) {
        if (!ROOT(i)) {
            children[par[i]].emplace_back(i, 0);
            childrenPull[par[i]].insert(0);
        }
        all_answer.insert(curans[i] = 0);
    }
    F(i, 1, n+1) if (~par[i]) {
        sort(A(children[i]));
    }

    auto upd = [&](ll i, ll we) {
        ll cur = belong[i];
        curw[cur] -= w[i];
        w[i] = we;
        curw[cur] += w[i];
        // assert(par[down[cur]] != down[cur]);
        recompute(par[down[cur]], down[cur]);
    };

    F(i, 0, n-1) upd(i, weights[i]);

    ll last = 0;

    while (q--) {
        G(d) G(e)
        d = (d + last)%(n-1);
        e = (e + last)%W;

        upd(d, e);

        last = all_answer.maximum();
        cout << last << '\n';
    }
}

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