Submission #884374

#	Time	Username	Problem	Language	Result	Execution time	Memory
884374		mgl_diamond	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	411 ms	226560 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define int long long
#define file "input"

template<class T> bool minimize(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool maximize(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const ll LINF = 1e18;
const int MOD = 998244353;
const int N = 6e5+5;

struct node {
  ll mat[3][3];
  node() { foru(i, 0, 2) foru(j, i, 2) mat[i][j] = -LINF; }
} sgt[N<<2];

int n, m;
ll W, ew[N], dist[N], lazy[N];
int eu[N], ev[N], st[N], en[N], euler[N], par[N];
vector<int> adj[N];

int cnt;
void dfs_first(int u, int p) {
  euler[++cnt] = u;
  st[u] = cnt;
  fore(i, adj[u]) {
    int v = eu[i]^ev[i]^u;
    if (v == p) continue;
    dist[v] = dist[u] + ew[i];
    par[v] = u;
    dfs_first(v, u);
    euler[++cnt] = u;
  }
  en[u] = cnt;
}

void apply(int id, ll val) {
  lazy[id] += val;
  foru(i, 0, 2) foru(j, i, 2) {
    int ad = 0;
    if (i == 0) ad += 1;
    if (i <= 1 && 1 <= j) ad -= 2;
    if (j == 2) ad += 1;
    sgt[id].mat[i][j] += val * ad;
  }
}

void push(int id) {
  if (lazy[id] == 0) return;
  apply(id*2, lazy[id]);
  apply(id*2+1, lazy[id]);
  lazy[id] = 0;
}

node comb(node a, node b) {
  node c;
  foru(i, 0, 2)
    foru(j, i, 2) {
      c.mat[i][j] = max(a.mat[i][j], b.mat[i][j]);
      foru(k, i, j-1) maximize(c.mat[i][j], a.mat[i][k] + b.mat[k+1][j]);
    }
  return c;
}

void build(int id = 1, int lb = 1, int rb = cnt) {
  if (lb ^ rb) {
    int k = id << 1, mb = (lb + rb) >> 1;
    build(k, lb, mb);
    build(k+1, mb+1, rb);
    sgt[id] = comb(sgt[k], sgt[k+1]);
  }
  else {
    sgt[id].mat[0][0] = dist[euler[lb]];
    sgt[id].mat[1][1] = -2 * dist[euler[lb]];
    sgt[id].mat[0][1] = sgt[id].mat[0][0] + sgt[id].mat[1][1];
    sgt[id].mat[1][2] = sgt[id].mat[1][1] + sgt[id].mat[2][2];
    sgt[id].mat[2][2] = dist[euler[lb]];
    sgt[id].mat[0][2] = 0;
  }
  // cout << lb << " " << rb << " " << sgt[id].mat[1][1] << "\n";
}

void update(int l, int r, ll val, int id = 1, int lb = 1, int rb = cnt) {
  if (l <= lb && rb <= r) {
    apply(id, val);
    return;
  }
  if (rb < l || lb > r) {
    return;
  }
  int k = id << 1, mb = (lb + rb) >> 1;
  push(id);
  update(l, r, val, k, lb, mb);
  update(l, r, val, k+1, mb+1, rb);
  sgt[id] = comb(sgt[k], sgt[k+1]);
  // cout << lb << " " << rb << " " << sgt[id].mat[0][1] << "\n";
}

signed main() {
  setIO();

  cin >> n >> m >> W;

  foru(i, 0, n-2) {
    cin >> eu[i] >> ev[i] >> ew[i];
    adj[eu[i]].push_back(i);
    adj[ev[i]].push_back(i);
  }

  dfs_first(1, 0);
  build();

  ll lst = 0;
  foru(z, 1, m) {
    ll x, y;
    cin >> x >> y;
    x = (x+lst) % (n-1);
    y = (y+lst) % W;
    if (par[eu[x]] == ev[x]) swap(eu[x], ev[x]);

    update(st[ev[x]], en[ev[x]], y - ew[x]);
    ew[x] = y;
    lst = sgt[1].mat[0][2];
    cout << lst << "\n";
  }
}

Compilation message (stderr)

diameter.cpp: In function 'void setIO()':
diameter.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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