Submission #877191

#TimeUsernameProblemLanguageResultExecution timeMemory
877191fanwenDynamic Diameter (CEOI19_diameter)C++17
49 / 100
865 ms17748 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define file(name) \ if(fopen(name".inp", "r")) \ freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \ const int MAX = 1e5 + 5; #define int long long struct Edge { int u, v; ll w; Edge(int u = 0, int v = 0, ll w = 0) : u(u), v(v), w(w) {} int get(int x) { return x ^ u ^ v; } } e[MAX]; int n, q; ll W; vector <int> adj[MAX]; namespace sub12 { bool check() { return max(n, q) <= 5000; } pair <ll, ll> dp[MAX]; void dfs(int u, int p) { dp[u] = make_pair(0, 0); for (int i : adj[u]) if(e[i].get(u) != p) { int v = e[i].get(u); dfs(v, u); if(dp[u].fi < dp[v].fi + e[i].w) { dp[u].se = dp[u].fi; dp[u].fi = dp[v].fi + e[i].w; } else { dp[u].se = max(dp[u].se, dp[v].fi + e[i].w); } } } ll get_diameter() { dfs(1, 0); ll ans = 0; for (int i = 1; i <= n; ++i) { ans = max(ans, dp[i].fi + dp[i].se); } return ans; } void solve() { ll last = 0; while(q--) { int d; ll f; cin >> d >> f; d = (d + last % (n - 1)) % (n - 1) + 1; f = (f + last) % W; e[d].w = f; last = get_diameter(); cout << last << '\n'; } exit(0); } } namespace sub3 { bool check() { return (int) adj[1].size() == n - 1; } template < class T, T (*f) (T, T), T (*e) ()> struct segment_tree { vector <T> it; int n; void set(int u, T p) { u--; for (it[u += n] = p; u >>= 1; ) { it[u] = f(it[u << 1], it[u << 1 | 1]); } } T get(int p) { return it[p += n - 1]; } T get(int l, int r) { l--; T resl = e(), resr = e(); for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) resl = f(resl, it[l++]); if(r & 1) resr = f(it[--r], resr); } return f(resl, resr); } T get_all() { return it[1]; } segment_tree(int n = 0) : n(n), it(n << 1 | 1) { fill(it.begin(), it.end(), T{}); } }; pair <ll, ll> _max_(pair <ll, ll> a, pair <ll, ll> b) { pair <ll, ll> res(a.fi, b.fi); if(res.fi < res.se) swap(res.fi, res.se); res.se = max(res.se, a.se); res.se = max(res.se, b.se); return res; } pair <ll, ll> E() { return make_pair(0, 0); } void solve() { segment_tree <pair <ll, ll>, _max_, E> it(n); for (int i : adj[1]) { it.set(e[i].get(1), make_pair(e[i].w, 0LL)); } auto get_diameter = [&] () -> ll { auto res = it.get_all(); return res.fi + res.se; }; ll last = 0; while(q--) { int d; ll f; cin >> d >> f; d = (d + last % (n - 1)) % (n - 1) + 1; f = (f + last) % W; e[d].w = f; it.set(e[d].get(1), make_pair(f, 0LL)); last = get_diameter(); cout << last << '\n'; } exit(0); } } namespace sub4 { template < class T, T (*f) (T, T), T (*e) ()> struct segment_tree { vector <T> it; int n; void set(int u, T p) { u--; for (it[u += n] = p; u >>= 1; ) { it[u] = f(it[u << 1], it[u << 1 | 1]); } } T get(int p) { return it[p += n - 1]; } T get(int l, int r) { l--; T resl = e(), resr = e(); for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) resl = f(resl, it[l++]); if(r & 1) resr = f(it[--r], resr); } return f(resl, resr); } segment_tree(int n = 0) : n(n), it(n << 1 | 1) { fill(it.begin(), it.end(), T{}); } }; ll op(ll a, ll b) { return a > b ? a : b; } ll E() { return numeric_limits<ll>::min(); } bool check() { for (int i = 1; i < n; ++i) { if(e[i].u > e[i].v) swap(e[i].u, e[i].v); if(e[i].v / 2 != e[i].u) return false; } return true; } pair <ll, ll> dp[MAX]; int par[MAX]; void dfs(int u, int p) { dp[u] = make_pair(0, 0); int cnt = 0; sort(adj[u].begin(), adj[u].end(), [&] (const int &x, const int &y) { return e[x].get(u) < e[y].get(u); }); for (int i : adj[u]) if(e[i].get(u) != p) { int v = e[i].get(u); par[v] = i; dfs(v, u); if(cnt == 0) { dp[u].fi = max(dp[v].fi, dp[v].se) + e[i].w; assert((u << 1) == v); } else { dp[u].se = max(dp[v].fi, dp[v].se) + e[i].w; assert((u << 1 | 1) == v); } ++cnt; } } void solve() { dfs(1, 0); segment_tree <ll, op, E> it(n); for (int i = 1; i <= n; ++i) it.set(i, dp[i].fi + dp[i].se); ll last = 0; while(q--) { int d; ll f; cin >> d >> f; d = (d + last % (n - 1)) % (n - 1) + 1; f = (f + last) % W; e[d].w = f; int u = e[d].v; while(u != 1) { int p = e[par[u]].get(u); if((p << 1 | 1) == u) { dp[p].se = max(dp[u].fi, dp[u].se) + e[par[u]].w; } else { assert((p << 1) == u); dp[p].fi = max(dp[u].fi, dp[u].se) + e[par[u]].w; } u = p; it.set(u, dp[u].fi + dp[u].se); } last = it.get(1, n); cout << last << '\n'; } exit(0); } } void you_make_it(void) { cin >> n >> q >> W; for (int i = 1; i < n; ++i) { int u, v, w; cin >> u >> v >> w; adj[u].push_back(i); adj[v].push_back(i); e[i] = Edge(u, v, w); } if(sub4::check()) sub4::solve(); if(sub3::check()) sub3::solve(); if(sub12::check()) sub12::solve(); } signed main() { #ifdef LOCAL freopen("TASK.inp", "r", stdin); freopen("TASK.out", "w", stdout); #endif file("diameter"); auto start_time = chrono::steady_clock::now(); cin.tie(0), cout.tie(0) -> sync_with_stdio(0); you_make_it(); auto end_time = chrono::steady_clock::now(); cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl; return (0 ^ 0); } // Dream it. Wish it. Do it.

Compilation message (stderr)

diameter.cpp: In instantiation of 'sub3::segment_tree<T, f, e>::segment_tree(long long int) [with T = std::pair<long long int, long long int>; T (* f)(T, T) = sub3::_max_; T (* e)() = sub3::E]':
diameter.cpp:125:52:   required from here
diameter.cpp:83:13: warning: 'sub3::segment_tree<std::pair<long long int, long long int>, sub3::_max_, sub3::E>::n' will be initialized after [-Wreorder]
   83 |         int n;
      |             ^
diameter.cpp:82:20: warning:   'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > > sub3::segment_tree<std::pair<long long int, long long int>, sub3::_max_, sub3::E>::it' [-Wreorder]
   82 |         vector <T> it;
      |                    ^~
diameter.cpp:110:9: warning:   when initialized here [-Wreorder]
  110 |         segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
      |         ^~~~~~~~~~~~
diameter.cpp: In instantiation of 'sub4::segment_tree<T, f, e>::segment_tree(long long int) [with T = long long int; T (* f)(T, T) = sub4::op; T (* e)() = sub4::E]':
diameter.cpp:222:38:   required from here
diameter.cpp:156:13: warning: 'sub4::segment_tree<long long int, sub4::op, sub4::E>::n' will be initialized after [-Wreorder]
  156 |         int n;
      |             ^
diameter.cpp:155:20: warning:   'std::vector<long long int> sub4::segment_tree<long long int, sub4::op, sub4::E>::it' [-Wreorder]
  155 |         vector <T> it;
      |                    ^~
diameter.cpp:179:9: warning:   when initialized here [-Wreorder]
  179 |         segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
      |         ^~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:269:5: note: in expansion of macro 'file'
  269 |     file("diameter");
      |     ^~~~
diameter.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); \
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:269:5: note: in expansion of macro 'file'
  269 |     file("diameter");
      |     ^~~~
#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...