제출 #518612

#제출 시각아이디문제언어결과실행 시간메모리
518612MonarchuwuDynamic Diameter (CEOI19_diameter)C++17
49 / 100
1426 ms17596 KiB
#include<iostream> #include<algorithm> #include<vector> #include<set> #define all(x) x.begin(), x.end() using namespace std; typedef long long ll; typedef pair<int, ll> pil; #define ff first #define ss second const int N = 1e5 + 9; int n, q; ll w, c; vector<int> g[N]; struct Edge { int u, v; ll w; int operator()(int x) { return u ^ v ^ x; } } e[N]; namespace subtask12 { vector<ll> a[N]; void dfs(int u, int p) { a[u].assign(2, 0); for (int id : g[u]) if (p != id) { int v = e[id](u); dfs(v, id); a[u].push_back(a[v][0] + e[id].w); } sort(all(a[u]), greater<ll>()); } ll gogo() { dfs(1, 0); ll ans(0); for (int i = 1; i <= n; ++i) ans = max(ans, a[i][0] + a[i][1]); return ans; } void solve() { int d; ll ee, last(0); while (q--) { cin >> d >> ee; d = (d + last) % (n - 1); ee = (ee + last) % w; e[d + 1].w = ee; last = gogo(); cout << last << '\n'; } } } namespace subtask3 { void solve() { multiset<int, greater<int>> s; for (int i = 1; i < n; ++i) s.insert(e[i].w); int d, ee, last(0); while (q--) { cin >> d >> ee; d = (d + last) % (n - 1); ee = (ee + last) % w; s.erase(s.find(e[d + 1].w)); s.insert(e[d + 1].w = ee); last = *s.begin() + *next(s.begin()); cout << last << '\n'; } } } namespace subtask4 { bool check() { for (int i = 1; i < n; ++i) if (e[i].v / 2 != e[i].u) return false; return true; } struct Node { ll path, diam; } seg[1 << 18]; ll wei[N]; void build(int u) { if (u > n) return; if (u * 2 > n) seg[u].path = seg[u].diam = wei[u]; else { int u1 = u << 1, u2 = u1 | 1; build(u1); build(u2); seg[u].path = max(seg[u1].path, seg[u2].path) + wei[u]; seg[u].diam = max({ seg[u1].diam, seg[u2].diam, seg[u1].path + seg[u2].path }); } } void upd(int u) { if (u * 2 > n) seg[u].path = seg[u].diam = wei[u]; else { int u1 = u << 1, u2 = u1 | 1; seg[u].path = max(seg[u1].path, seg[u2].path) + wei[u]; } for (u >>= 1; u; u >>= 1) { int u1 = u << 1, u2 = u1 | 1; seg[u].path = max(seg[u1].path, seg[u2].path) + wei[u]; seg[u].diam = max({ seg[u1].diam, seg[u2].diam, seg[u1].path + seg[u2].path }); } } void solve() { wei[1] = 0; for (int i = 1; i < n; ++i) wei[e[i].v] = e[i].w; build(1); int d; ll ee, last(0); while (q--) { cin >> d >> ee; d = (d + last) % (n - 1); ee = (ee + last) % w; wei[e[d + 1].v] = ee; upd(e[d + 1].v); last = seg[1].diam; cout << last << '\n'; } } } int main() { cin.tie(NULL)->sync_with_stdio(false); cin >> n >> q >> w; for (int i = 1, u, v; i < n; ++i) { cin >> e[i].u >> e[i].v >> e[i].w; if (e[i].u > e[i].v) swap(e[i].u, e[i].v); g[e[i].u].push_back(i); g[e[i].v].push_back(i); } if (n <= 5000 && q <= 5000) subtask12::solve(); else if (g[1].size() == n - 1) subtask3::solve(); else if (subtask4::check()) subtask4::solve(); } /** /\_/\ * (= ._.) * / >0 \>1 **/

컴파일 시 표준 에러 (stderr) 메시지

diameter.cpp: In function 'int main()':
diameter.cpp:136:21: warning: unused variable 'u' [-Wunused-variable]
  136 |     for (int i = 1, u, v; i < n; ++i) {
      |                     ^
diameter.cpp:136:24: warning: unused variable 'v' [-Wunused-variable]
  136 |     for (int i = 1, u, v; i < n; ++i) {
      |                        ^
diameter.cpp:144:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  144 |     else if (g[1].size() == n - 1) subtask3::solve();
      |              ~~~~~~~~~~~~^~~~~~~~
#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...