Submission #922374

#TimeUsernameProblemLanguageResultExecution timeMemory
922374SNP011Dynamic Diameter (CEOI19_diameter)C++17
7 / 100
489 ms60332 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<long long, long long> #define pb push_back const int maxn = 2e5 + 5; int h[maxn], dp[5][4 * maxn], lastans; int lazy[4 * maxn], st[maxn], fn[maxn]; vector<pii> adj[maxn]; vector<int> discovery; map<pii, int> we; void dfs(int v, int par = 0) { st[v] = 1ll * discovery.size(); discovery.pb(h[v]); for (auto[w, u]: adj[v]) { if (u != par) { h[u] = h[v] + w; dfs(u, v); discovery.pb(h[v]); } } fn[v] = 1ll * discovery.size() - 1; } void updateDP(int id) { dp[0][id] = max({dp[0][2 * id], dp[0][2 * id + 1], dp[2][2 * id] + dp[4][2 * id + 1], dp[3][2 * id] + dp[2][2 * id + 1]}); dp[1][id] = min(dp[1][2 * id], dp[1][2 * id + 1]); dp[2][id] = max(dp[2][2 * id], dp[2][2 * id + 1]); dp[3][id] = max({dp[3][2 * id], dp[3][2 * id + 1], dp[2][2 * id] - (2 * dp[1][2 * id + 1])}); dp[4][id] = max({dp[4][2 * id], dp[4][2 * id + 1], dp[2][2 * id + 1] - (2 * dp[1][2 * id])}); } struct segment { void init(int id, int L, int R) { if (L + 1 == R) { if (1ll * discovery.size() >= L) { dp[1][id] = discovery[L]; dp[2][id] = discovery[L]; } return; } int mid = (R + L) >> 1; init(2 * id, L, mid); init(2 * id + 1, mid, R); updateDP(id); } void spread(int id, int L, int R) { int mid = (R + L) >> 1; dp[1][2 * id] += lazy[id]; dp[2][2 * id] += lazy[id]; if (mid - L >= 2) { dp[3][2 * id] -= lazy[id]; dp[4][2 * id] -= lazy[id]; } dp[1][2 * id + 1] += lazy[id]; dp[2][2 * id + 1] += lazy[id]; if (R - mid >= 2) { dp[3][2 * id + 1] -= lazy[id]; dp[4][2 * id + 1] -= lazy[id]; } lazy[2 * id] += lazy[id]; lazy[2 * id + 1] += lazy[id]; lazy[id] = 0; } void update(int id, int L, int R, int l, int r, int val) { if (L == l and R == r) { dp[1][id] += val; dp[2][id] += val; if (R - L >= 2) { dp[3][id] -= val; dp[4][id] -= val; } lazy[id] += val; return; } spread(id, L, R); int mid = (R + L) >> 1; if (l < mid) { update(2 * id, L, mid, l, min(r, mid), val); } if (r > mid) { update(2 * id + 1, mid, R, max(l, mid), r, val); } updateDP(id); } } seg; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, q, w; cin >> n >> q >> w; vector<pii> edge; for (int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; adj[v].pb({w, u}); adj[u].pb({w, v}); we[{u, v}] = w; we[{v, u}] = w; edge.pb({u, v}); } discovery.pb(-1); dfs(1); seg.init(1, 1, maxn); while (q--) { int d, e; cin >> d >> e; d = (d + lastans) % (n - 1); e = (e + lastans) % w; // cout << d << ", " << e << ": "; int u = edge[d].first, v = edge[d].second; if (h[u] < h[v]) { swap(u, v); } // h[u] >= h[v] seg.update(1, 1, maxn, st[u], fn[u] + 1, e - we[edge[d]]); // cout << e - we[{edge[d]}] << "->" << st[u] << ", " << fn[u] << '\n'; we[{u, v}] = e; we[{v, u}] = e; lastans = dp[0][1]; cout << dp[0][1] << '\n'; } return 0; }

Compilation message (stderr)

diameter.cpp: In member function 'void segment::init(long long int, long long int, long long int)':
diameter.cpp:40:31: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   40 |    if (1ll * discovery.size() >= L) {
      |        ~~~~~~~~~~~~~~~~~~~~~~~^~~~
#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...