Submission #872823

#TimeUsernameProblemLanguageResultExecution timeMemory
872823bobbilykingDynamic Diameter (CEOI19_diameter)C++17
49 / 100
5032 ms37716 KiB
#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) { // 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]); if (!ROOT(i)) recompute(par[i], i); } 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); } } F(i, 1, n+1) if (~par[i]) { sort(A(children[i])); if (children[i].size()) { all_answer.insert(curans[i] = 0); } } set<ll> toprocess; F(i, 0, n-1) { curw[belong[i]] += (w[i] = weights[i]); toprocess.insert(belong[i]); } for (const auto cur: toprocess) { recompute(par[down[cur]], down[cur]); } 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'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...