Submission #1095997

#TimeUsernameProblemLanguageResultExecution timeMemory
1095997yoav_sDynamic Diameter (CEOI19_diameter)C++17
0 / 100
5060 ms26992 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> v; typedef vector<v> vv; typedef vector<vv> vvv; typedef pair<ll, ll> p; typedef vector<p> vp; typedef vector<vp> vvp; typedef vector<vvp> vvvp; typedef pair<ll, p> tri; typedef vector<tri> vtri; typedef vector<vtri> vvtri; typedef vector<vvtri> vvvtri; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; #define f first #define s second #define pb push_back #define eb emplace_back #define all(v) (v).begin(),(v).end() const ll INF = 1e18; const ll mod = 1e9 + 7; void findFurtherest(vvp &graph, v &weights, vp &res, ll i) { res[i] = p(0, i); for (auto x : graph[i]) { if (res[x.f].f == -1) { findFurtherest(graph, weights, res, x.f); res[i] = max(res[i], p(res[x.f].f + weights[x.s], res[x.f].s)); } } } void getRes(vvp &graph, v &weights, vp &furtherest, ll i, vb &visited, v &res) { if (visited[i]) return; visited[i] = true; ll curMaxi = furtherest[i].f; v children; for (auto x : graph[i]) { if (!visited[x.f]) { children.pb(furtherest[x.f].f + weights[x.s]); getRes(graph, weights, furtherest, x.f, visited, res); } } sort(all(children),greater<ll>()); if (children.size() >= 2) curMaxi = max(curMaxi, children[0] + children[1]); res[i] = curMaxi; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll n, q, w; cin >> n >> q >> w; vtri edges(n - 1); for (ll i = 0; i < n - 1; i++) { cin >> edges[i].s.f >> edges[i].s.s >> edges[i].f; edges[i].s.f--; edges[i].s.s--; } v weight(n - 1); for (ll i = 0; i < n - 1; i++) weight[i] = edges[i].f; vvp graph(n); for (ll i = 0; i < n - 1; i++) { graph[edges[i].s.f].eb(edges[i].s.s, i); graph[edges[i].s.s].eb(edges[i].s.f, i); } v parent(n, -1); stack<p> dfs; dfs.emplace(0, 0); while (!dfs.empty()) { auto top = dfs.top(); dfs.pop(); if (parent[top.f] != -1) continue; parent[top.f] = top.s; for (auto x : graph[top.f]) dfs.emplace(x.f, top.f); } vvp dirGraph(n); for (ll i =0 ; i < n; i++) { for (auto x : graph[i]) if (x.f != parent[i]) dirGraph[i].pb(x); } ll last = 0; vp furtherest(n, p(-1,-1)); findFurtherest(graph, weight, furtherest, 0); multiset<ll> values; v res(n, -1); vb visited(n, false); getRes(graph, weight, furtherest, 0, visited, res); multiset<ll,greater<ll>> reses; for (ll x : res) reses.insert(x); while (q--) { ll d, e; cin >> d >> e; d = (d + last) % (n - 1); e = (e + last) % w; weight[d] = e; ll cur = d; while (true) { furtherest[cur] = p(0, cur); for (auto x : dirGraph[cur]) { furtherest[cur] = max(furtherest[cur], p(furtherest[x.f].f + weight[x.s], furtherest[x.f].s)); } reses.erase(reses.find(res[cur])); ll curMaxi = furtherest[cur].f; v children; for (auto x : dirGraph[cur]) { children.pb(furtherest[x.f].f + weight[x.s]); } sort(all(children),greater<ll>()); if (children.size() >= 2) curMaxi = max(curMaxi, children[0] + children[1]); res[cur] = curMaxi; reses.insert(curMaxi); if (cur == 0) break; cur = parent[cur]; } vb visited(n, false); last = *reses.begin(); cout << last << "\n"; } return 0; }
#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...