Submission #980037

#	Time	Username	Problem	Language	Result	Execution time	Memory
980037		duckindog	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	1202 ms	45908 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 100'000 + 10;
int n, q, maxW;
vector<pair<int, int>> ad[N];
struct Edge { 
  int u, v, w;

  friend istream& operator >> (istream& is, auto& rhs) { 
    return is >> rhs.u >> rhs.v >> rhs.w;
  }
} edge[N];

int sz[N], par[N];
void dfs1(int u, int p = -1) { 
  for (const auto& [v, w] : ad[u]) { 
    if (v == p) continue;
    par[v] = u;
    dfs1(v, u);
    sz[u] += sz[v] + 1;
  }
}

int head[N], st[N], ed[N], rvs[N], it;
void hld(int u, int p = -1) { 
  if (!head[u]) head[u] = u;
  st[u] = ++it; rvs[it] = u;

  sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) { 
    return sz[a.first] > sz[b.first];
  });

  bool heavy = false;
  for (const auto& [v, w] : ad[u]) { 
    if (v == p) continue;

    if (!heavy) head[v] = head[u], hld(v, u);
    else hld(v, u);
    heavy = true;
  }

  ed[u] = it;
}

struct IT { 
  int f[N << 2], lazy[N << 2];

  void push(int s) { 
    f[s << 1] += lazy[s];     f[s << 1 | 1] += lazy[s];
    lazy[s << 1] += lazy[s];  lazy[s << 1 | 1] += lazy[s];
    lazy[s] = 0;
  }
  void update(int s, int l, int r, int u, int v, int x) { 
    if (v < l || u > r) return;
    if (u <= l && r <= v) { 
      f[s] += x;
      lazy[s] += x;
      return;
    }
    push(s);
    int mid = l + r >> 1;
    update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x);
    f[s] = max(f[s << 1], f[s << 1 | 1]);
  }
  void assign(int s, int l, int r, int i, int x) { 
    if (i < l || i > r) return;
    if (l == r) { 
      f[s] = x;
      lazy[s] = 0;
      return;
    }
    push(s);
    int mid = l + r >> 1;
    assign(s << 1, l, mid, i, x); assign(s << 1 | 1, mid + 1, r, i, x);
    f[s] = max(f[s << 1], f[s << 1 | 1]);
  }
  int query(int s, int l, int r, int u, int v) { 
    if (v < l || u > r) return -20'000'000'000'000'000;
    if (u <= l && r <= v) return f[s];
    push(s);
    int mid = l + r >> 1;
    return max(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
  }
  int lower_bound(int s, int l, int r, int x) { 
    if (l == r) return l;
    push(s);
    int mid = l + r >> 1;
    if (f[s << 1] >= x) return lower_bound(s << 1, l, mid, x);
    return lower_bound(s << 1 | 1, mid + 1, r, x);
  }
} D, T;

void dfs2(int u, int p = -1) { 
  for (const auto& [v, w] : ad[u]) { 
    if (v == p) continue;
    D.update(1, 1, n, st[v], ed[v], w);
    dfs2(v, u);
  }
  T.update(1, 1, n, st[u], st[u], -2 * D.query(1, 1, n, st[u], st[u]));
  int heavy = (ad[u].size() - (u != 1) <= 1 ? 0 : ad[u][u != 1].first);
  if (!heavy) return;
  T.update(1, 1, n, st[u], st[u], D.query(1, 1, n, ed[heavy] + 1, ed[u]));
}

void update(int i, int nW) { 
  auto [u, v, w] = edge[i];
  edge[i].w = nW;
  if (st[u] > st[v] ) swap(u, v);
  
  D.update(1, 1, n, st[v], ed[v], nW - w);
  T.update(1, 1, n, st[v], ed[v], w - nW);

  while (u) { 
    T.assign(1, 1, n, st[u], 0);
    T.update(1, 1, n, st[u], st[u], -2 * D.query(1, 1, n, st[u], st[u]));
    int heavy = (ad[u].size() - (u != 1) <= 1 ? 0 : ad[u][u != 1].first);
    if (heavy)
      T.update(1, 1, n, st[u], st[u], D.query(1, 1, n, ed[heavy] + 1, ed[u]));
    
    if (u == 1) break;
    u = par[head[u]];
  }
}
int get() { 
  int d = D.f[1],
      u = rvs[D.lower_bound(1, 1, n, d)],
      ret = 0;
  
  while (u) {
    int minus = 2 * D.query(1, 1, n, st[par[head[u]]], st[par[head[u]]]);
    ret = max(ret, T.query(1, 1, n, st[head[u]], st[u] - 1));
    ret = max(ret, D.query(1, 1, n, st[par[head[u]]], st[head[u]] - 1) - minus);
    ret = max(ret, D.query(1, 1, n, ed[head[u]] + 1, ed[par[head[u]]]) - minus);

    if (u == 1) break;
    u = par[head[u]];
  }
  
  return ret + d;
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> q >> maxW;
  for (int i = 0; i < n - 1; ++i) {
    cin >> edge[i];
    const auto& [u, v, w] = edge[i];
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
  }

  dfs1(par[1] = 1); hld(1);

  dfs2(1);
  
  int siesta = 0;
  while (q--) { 
    int i, nW; cin >> i >> nW;
    i = (i + siesta) % (n - 1);
    nW = (nW + siesta) % maxW;
    
    update(i, nW);
    cout << (siesta = get()) << "\n";
  }
}

Compilation message (stderr)

diameter.cpp:13:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   13 |   friend istream& operator >> (istream& is, auto& rhs) {
      |                                             ^~~~
diameter.cpp: In member function 'void IT::update(long long int, long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int mid = l + r >> 1;
      |               ~~^~~
diameter.cpp: In member function 'void IT::assign(long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:77:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     int mid = l + r >> 1;
      |               ~~^~~
diameter.cpp: In member function 'long long int IT::query(long long int, long long int, long long int, long long int, long long int)':
diameter.cpp:85:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int mid = l + r >> 1;
      |               ~~^~~
diameter.cpp: In member function 'long long int IT::lower_bound(long long int, long long int, long long int, long long int)':
diameter.cpp:91:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |     int mid = l + r >> 1;
      |               ~~^~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27