oj.uz

Submission #531153

# Submission time Handle Problem Language Result Execution time Memory
531153 2022-02-27T21:20:20 Z Alex_tz307 Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 4894 ms 377832 KB 
#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5;
multiset<int64_t> diameters{0};

void maxSelf(int64_t &x, int64_t y) {
  if (x < y) {
    x = y;
  }
}

struct Centroid {
  int n, root, timer;
  vector<int> nodes, tin, tout, child, dep;
  vector<tuple<int, int, int64_t>> edges;
  vector<vector<int>> g;
  vector<int64_t> wt, dp, maxDist, dpLin;
  multiset<int64_t> paths;

  struct ST {
    int n;
    vector<int64_t> t, lazy, dp;

    void init(int N, const vector<int64_t> &aux) {
      n = N;
      int dim = 1;
      while (dim < n) {
        dim *= 2;
      }
      dim *= 2;
      t.resize(dim);
      lazy.resize(dim);
      dp = aux;
    }

    void build(int x, int lx, int rx) {
      if (lx == rx) {
        t[x] = dp[lx];
        return;
      }
      int mid = (lx + rx) / 2;
      build(x * 2, lx, mid);
      build(x * 2 + 1, mid + 1, rx);
      t[x] = max(t[x * 2], t[x * 2 + 1]);
    }

    void updateNode(int x, int64_t v) {
      t[x] += v;
      lazy[x] += v;
    }

    void push(int x) {
      if (lazy[x] == 0) {
        return;
      }
      for (int i = 0; i < 2; ++i) {
        updateNode(x * 2 + i, lazy[x]);
      }
      lazy[x] = 0;
    }

    void update(int x, int lx, int rx, int st, int dr, int64_t v) {
      if (st <= lx && rx <= dr) {
        updateNode(x, v);
        return;
      }
      push(x);
      int mid = (lx + rx) / 2;
      if (st <= mid) {
        update(x * 2, lx, mid, st, dr, v);
      }
      if (mid < dr) {
        update(x * 2 + 1, mid + 1, rx, st, dr, v);
      }
      t[x] = max(t[x * 2], t[x * 2 + 1]);
    }

    void update(int st, int dr, int64_t v) {
      update(1, 1, n, st, dr, v);
    }

    int64_t query(int x, int lx, int rx, int st, int dr) {
      if (st <= lx && rx <= dr) {
        return t[x];
      }
      push(x);
      int mid = (lx + rx) / 2;
      int64_t ans = 0;
      if (st <= mid) {
        maxSelf(ans, query(x * 2, lx, mid, st, dr));
      }
      if (mid < dr) {
        maxSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr));
      }
      return ans;
    }

    int64_t query(int st, int dr) {
      return query(1, 1, n, st, dr);
    }
  } t;

  void setRoot(int v) {
    root = v;
  }

  void addNode(int v) {
    nodes.emplace_back(v);
  }

  void addEdge(int u, int v, int64_t w) {
    edges.emplace_back(u, v, w);
  }

  int getIndex(int v) {
    return distance(nodes.begin(), upper_bound(nodes.begin(), nodes.end(), v));
  }

  void dfs(int u, int par) {
    tin[u] = ++timer;
    maxDist[u] = dp[u];
    for (int v : g[u]) {
      if (v != par) {
        if (par == 0) {
          child[v] = v;
        } else {
          child[v] = child[u];
        }
        dep[v] = dep[u] + 1;
        dp[v] = dp[u] + wt[v];
        dfs(v, u);
        maxSelf(maxDist[u], maxDist[v]);
      }
    }
    tout[u] = timer;
  }

  int64_t getDiameter(int dbg) {
    auto it = paths.end();
    --it;
    int64_t len = *it;
    if ((int)paths.size() >= 2) {
      --it;
      len += *it;
    }
    /* if (dbg == 100) {
      cout << endl;
      cout << "ULTIMELE 2 SUNT " << *paths.rbegin() << ' ' << *prev(paths.rbegin()) << endl;
      for (auto it : paths) {
        cout << it << ' ';
      }
      cout << endl << endl;
    }
    if (dbg == 100) {
      cout << "CEVA 100 " << endl;
      for (auto it : paths) {
        cout << it << ' ';
      }
      cout << endl;
    }
    if (dbg == 100) {
      cout << "ADAUG " << len << endl;
    } */
    return len;
  }

  void addDiameter(int dbg = 0) {
    /* if (dbg == 100) {
      cout << "CEVA " << endl;
      for (auto it : paths) {
        cout << it << ' ';
      }
      cout << endl;
    } */
    diameters.emplace(getDiameter(dbg));
  }

  void removeDiameter() {
    diameters.erase(diameters.find(getDiameter(1)));
  }
  /*
10 1 10000
1 9 1241
5 6 1630
10 5 1630
2 6 853
10 1 511
5 3 760
8 3 1076
4 10 1483
7 10 40
8 2051
  */

  /*
10 0 10000
1 9 1241
5 6 1630
10 5 1630
2 6 853
10 1 511
5 3 760
8 3 1076
4 10 1483
7 10 40
  */
  void build() {
    /// cout << "CONSTRUIESC ARBORELE CENTROIDULUI " << root << endl;
    /// cout << "AM " << nodes.size() << " NODURI" << endl;
    /// cout << endl;
    sort(nodes.begin(), nodes.end());
    root = getIndex(root);
    n = nodes.size();
    g.resize(n + 1);
    wt.resize(n + 1);
    for (auto it : edges) {
      int u, v;
      int64_t w;
      tie(u, v, w) = it;
      u = getIndex(u);
      v = getIndex(v);
      g[u].emplace_back(v);
      wt[v] = w;
    }
    timer = 0;
    tin.resize(n + 1);
    tout.resize(n + 1);
    dp.resize(n + 1);
    maxDist.resize(n + 1);
    child.resize(n + 1);
    dep.resize(n + 1);
    dfs(root, 0);
    dpLin.resize(n + 1);
    for (int v = 1; v <= n; ++v) {
      dpLin[tin[v]] = dp[v];
    }
    t.init(n, dpLin);
    t.build(1, 1, n);
    for (int v : g[root]) {
      paths.emplace(maxDist[v]);
    }
    addDiameter();
  }

  void updateEdge(int v, int64_t w) {
    ///cout << "CEVA" << endl;
    removeDiameter();
    v = getIndex(v);
    int son = child[v];
    ///cout << son << ' ' << v << endl;
    ///cout << wt[v] << endl;
    paths.erase(paths.find(t.query(tin[son], tout[son])));
    t.update(tin[v], tout[v], w - wt[v]);
    wt[v] = w;
    paths.emplace(t.query(tin[son], tout[son]));
    addDiameter(100);
  }
} C[1 + kN];

int sz[1 + kN];
vector<pair<int, int64_t>> g[1 + kN];
pair<int, int> edges[1 + kN];
bitset<1 + kN> vis;
map<pair<int, int>, vector<int>> centroids;

void findSize(int u, int par) {
  sz[u] = 1;
  for (auto it : g[u]) {
    int v = it.first;
    if (!vis[v] && v != par) {
      findSize(v, u);
      sz[u] += sz[v];
    }
  }
}

int findCentroid(int u, int par, int n) {
  for (auto it : g[u]) {
    int v = it.first;
    if (!vis[v] && v != par && sz[v] > n / 2) {
      return findCentroid(v, u, n);
    }
  }
  return u;
}

void dfs(int u, int par, int centroid) {
  if (par) {
    centroids[{par, u}].emplace_back(centroid);
  }
  C[centroid].addNode(u);
  for (auto it : g[u]) {
    int v;
    int64_t w;
    tie(v, w) = it;
    if (!vis[v] && v != par) {
      C[centroid].addEdge(u, v, w);
      dfs(v, u, centroid);
    }
  }
}

void build(int u) {
  findSize(u, 0);
  if (sz[u] == 1) {
    return;
  }
  int c = findCentroid(u, 0, sz[u]);
  /// cout << "CENTROID " << c << endl;
  vis[c] = true;
  C[c].setRoot(c);
  dfs(c, 0, c);
  C[c].build();
  for (auto it : g[c]) {
    int v = it.first;
    if (!vis[v]) {
      build(v);
    }
  }
}

void testCase() {
  int n, q;
  int64_t W;
  cin >> n >> q >> W;
  for (int i = 1; i < n; ++i) {
    int u, v;
    int64_t w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
    edges[i] = {u, v};
  }
  build(1);
  int64_t last = 0;
  /// cout << *diameters.rbegin() << endl;
  for (int i = 1; i <= q; ++i) {
    int d;
    int64_t w;
    cin >> d >> w;
    d = (last + d) % (n - 1);
    w = (last + w) % W;
    d += 1;
    int u, v;
    tie(u, v) = edges[d];
    for (int c : centroids[{u, v}]) {
      C[c].updateEdge(v, w);
    }
    for (int c : centroids[{v, u}]) {
      C[c].updateEdge(u, w);
    }
    last = *diameters.rbegin();
    cout << last << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42484 KB Output is correct
2 Correct 20 ms 42504 KB Output is correct
3 Correct 22 ms 42596 KB Output is correct
4 Correct 21 ms 42596 KB Output is correct
5 Correct 21 ms 42596 KB Output is correct
6 Correct 25 ms 42572 KB Output is correct
7 Correct 20 ms 42572 KB Output is correct
8 Correct 20 ms 42568 KB Output is correct
9 Correct 21 ms 42600 KB Output is correct
10 Correct 21 ms 42692 KB Output is correct
11 Correct 20 ms 42572 KB Output is correct
12 Correct 23 ms 42588 KB Output is correct
13 Correct 21 ms 42640 KB Output is correct
14 Correct 21 ms 42572 KB Output is correct
15 Correct 21 ms 42584 KB Output is correct
16 Correct 24 ms 42600 KB Output is correct
17 Correct 20 ms 42692 KB Output is correct
18 Correct 20 ms 42636 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42484 KB Output is correct
2 Correct 20 ms 42504 KB Output is correct
3 Correct 22 ms 42596 KB Output is correct
4 Correct 21 ms 42596 KB Output is correct
5 Correct 21 ms 42596 KB Output is correct
6 Correct 25 ms 42572 KB Output is correct
7 Correct 20 ms 42572 KB Output is correct
8 Correct 20 ms 42568 KB Output is correct
9 Correct 21 ms 42600 KB Output is correct
10 Correct 21 ms 42692 KB Output is correct
11 Correct 20 ms 42572 KB Output is correct
12 Correct 23 ms 42588 KB Output is correct
13 Correct 21 ms 42640 KB Output is correct
14 Correct 21 ms 42572 KB Output is correct
15 Correct 21 ms 42584 KB Output is correct
16 Correct 24 ms 42600 KB Output is correct
17 Correct 20 ms 42692 KB Output is correct
18 Correct 20 ms 42636 KB Output is correct
19 Correct 41 ms 43868 KB Output is correct
20 Correct 43 ms 44012 KB Output is correct
21 Correct 50 ms 44232 KB Output is correct
22 Correct 49 ms 44532 KB Output is correct
23 Correct 68 ms 49884 KB Output is correct
24 Correct 81 ms 51816 KB Output is correct
25 Correct 97 ms 53164 KB Output is correct
26 Correct 99 ms 55744 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42544 KB Output is correct
2 Correct 21 ms 42536 KB Output is correct
3 Correct 21 ms 42580 KB Output is correct
4 Correct 31 ms 42760 KB Output is correct
5 Correct 81 ms 43732 KB Output is correct
6 Correct 21 ms 42600 KB Output is correct
7 Correct 21 ms 42756 KB Output is correct
8 Correct 21 ms 42716 KB Output is correct
9 Correct 24 ms 42820 KB Output is correct
10 Correct 39 ms 43076 KB Output is correct
11 Correct 109 ms 44064 KB Output is correct
12 Correct 25 ms 44500 KB Output is correct
13 Correct 25 ms 44492 KB Output is correct
14 Correct 32 ms 44652 KB Output is correct
15 Correct 53 ms 45060 KB Output is correct
16 Correct 152 ms 46328 KB Output is correct
17 Correct 123 ms 79592 KB Output is correct
18 Correct 127 ms 79576 KB Output is correct
19 Correct 128 ms 79656 KB Output is correct
20 Correct 179 ms 80720 KB Output is correct
21 Correct 578 ms 86144 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 44120 KB Output is correct
2 Correct 53 ms 44288 KB Output is correct
3 Correct 167 ms 44812 KB Output is correct
4 Correct 310 ms 45512 KB Output is correct
5 Correct 76 ms 63300 KB Output is correct
6 Correct 128 ms 63576 KB Output is correct
7 Correct 355 ms 64600 KB Output is correct
8 Correct 756 ms 65648 KB Output is correct
9 Correct 353 ms 163508 KB Output is correct
10 Correct 438 ms 163896 KB Output is correct
11 Correct 848 ms 165464 KB Output is correct
12 Correct 1345 ms 166708 KB Output is correct
13 Correct 761 ms 298876 KB Output is correct
14 Correct 859 ms 299340 KB Output is correct
15 Correct 1373 ms 300988 KB Output is correct
16 Correct 2021 ms 302500 KB Output is correct
17 Correct 3502 ms 303628 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3241 ms 263216 KB Output is correct
2 Correct 3343 ms 269984 KB Output is correct
3 Correct 3298 ms 267896 KB Output is correct
4 Correct 3404 ms 270040 KB Output is correct
5 Correct 3317 ms 255780 KB Output is correct
6 Correct 2646 ms 180440 KB Output is correct
7 Correct 4377 ms 330600 KB Output is correct
8 Correct 4415 ms 330632 KB Output is correct
9 Correct 4433 ms 330720 KB Output is correct
10 Correct 4365 ms 329120 KB Output is correct
11 Correct 4204 ms 310872 KB Output is correct
12 Correct 3457 ms 215732 KB Output is correct
13 Correct 4759 ms 377664 KB Output is correct
14 Correct 4743 ms 377760 KB Output is correct
15 Correct 4748 ms 377832 KB Output is correct
16 Correct 4832 ms 375712 KB Output is correct
17 Correct 4643 ms 352732 KB Output is correct
18 Correct 3488 ms 234276 KB Output is correct
19 Correct 4822 ms 377552 KB Output is correct
20 Correct 4834 ms 377544 KB Output is correct
21 Correct 4894 ms 377480 KB Output is correct
22 Correct 4866 ms 375644 KB Output is correct
23 Correct 4563 ms 352792 KB Output is correct
24 Correct 3500 ms 234436 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42484 KB Output is correct
2 Correct 20 ms 42504 KB Output is correct
3 Correct 22 ms 42596 KB Output is correct
4 Correct 21 ms 42596 KB Output is correct
5 Correct 21 ms 42596 KB Output is correct
6 Correct 25 ms 42572 KB Output is correct
7 Correct 20 ms 42572 KB Output is correct
8 Correct 20 ms 42568 KB Output is correct
9 Correct 21 ms 42600 KB Output is correct
10 Correct 21 ms 42692 KB Output is correct
11 Correct 20 ms 42572 KB Output is correct
12 Correct 23 ms 42588 KB Output is correct
13 Correct 21 ms 42640 KB Output is correct
14 Correct 21 ms 42572 KB Output is correct
15 Correct 21 ms 42584 KB Output is correct
16 Correct 24 ms 42600 KB Output is correct
17 Correct 20 ms 42692 KB Output is correct
18 Correct 20 ms 42636 KB Output is correct
19 Correct 41 ms 43868 KB Output is correct
20 Correct 43 ms 44012 KB Output is correct
21 Correct 50 ms 44232 KB Output is correct
22 Correct 49 ms 44532 KB Output is correct
23 Correct 68 ms 49884 KB Output is correct
24 Correct 81 ms 51816 KB Output is correct
25 Correct 97 ms 53164 KB Output is correct
26 Correct 99 ms 55744 KB Output is correct
27 Correct 20 ms 42544 KB Output is correct
28 Correct 21 ms 42536 KB Output is correct
29 Correct 21 ms 42580 KB Output is correct
30 Correct 31 ms 42760 KB Output is correct
31 Correct 81 ms 43732 KB Output is correct
32 Correct 21 ms 42600 KB Output is correct
33 Correct 21 ms 42756 KB Output is correct
34 Correct 21 ms 42716 KB Output is correct
35 Correct 24 ms 42820 KB Output is correct
36 Correct 39 ms 43076 KB Output is correct
37 Correct 109 ms 44064 KB Output is correct
38 Correct 25 ms 44500 KB Output is correct
39 Correct 25 ms 44492 KB Output is correct
40 Correct 32 ms 44652 KB Output is correct
41 Correct 53 ms 45060 KB Output is correct
42 Correct 152 ms 46328 KB Output is correct
43 Correct 123 ms 79592 KB Output is correct
44 Correct 127 ms 79576 KB Output is correct
45 Correct 128 ms 79656 KB Output is correct
46 Correct 179 ms 80720 KB Output is correct
47 Correct 578 ms 86144 KB Output is correct
48 Correct 26 ms 44120 KB Output is correct
49 Correct 53 ms 44288 KB Output is correct
50 Correct 167 ms 44812 KB Output is correct
51 Correct 310 ms 45512 KB Output is correct
52 Correct 76 ms 63300 KB Output is correct
53 Correct 128 ms 63576 KB Output is correct
54 Correct 355 ms 64600 KB Output is correct
55 Correct 756 ms 65648 KB Output is correct
56 Correct 353 ms 163508 KB Output is correct
57 Correct 438 ms 163896 KB Output is correct
58 Correct 848 ms 165464 KB Output is correct
59 Correct 1345 ms 166708 KB Output is correct
60 Correct 761 ms 298876 KB Output is correct
61 Correct 859 ms 299340 KB Output is correct
62 Correct 1373 ms 300988 KB Output is correct
63 Correct 2021 ms 302500 KB Output is correct
64 Correct 3502 ms 303628 KB Output is correct
65 Correct 3241 ms 263216 KB Output is correct
66 Correct 3343 ms 269984 KB Output is correct
67 Correct 3298 ms 267896 KB Output is correct
68 Correct 3404 ms 270040 KB Output is correct
69 Correct 3317 ms 255780 KB Output is correct
70 Correct 2646 ms 180440 KB Output is correct
71 Correct 4377 ms 330600 KB Output is correct
72 Correct 4415 ms 330632 KB Output is correct
73 Correct 4433 ms 330720 KB Output is correct
74 Correct 4365 ms 329120 KB Output is correct
75 Correct 4204 ms 310872 KB Output is correct
76 Correct 3457 ms 215732 KB Output is correct
77 Correct 4759 ms 377664 KB Output is correct
78 Correct 4743 ms 377760 KB Output is correct
79 Correct 4748 ms 377832 KB Output is correct
80 Correct 4832 ms 375712 KB Output is correct
81 Correct 4643 ms 352732 KB Output is correct
82 Correct 3488 ms 234276 KB Output is correct
83 Correct 4822 ms 377552 KB Output is correct
84 Correct 4834 ms 377544 KB Output is correct
85 Correct 4894 ms 377480 KB Output is correct
86 Correct 4866 ms 375644 KB Output is correct
87 Correct 4563 ms 352792 KB Output is correct
88 Correct 3500 ms 234436 KB Output is correct
89 Correct 3320 ms 265784 KB Output is correct
90 Correct 3722 ms 288964 KB Output is correct
91 Correct 4250 ms 320000 KB Output is correct
92 Correct 4472 ms 329852 KB Output is correct
93 Correct 4632 ms 344512 KB Output is correct
94 Correct 4608 ms 356628 KB Output is correct
95 Correct 4806 ms 376672 KB Output is correct
96 Correct 4775 ms 376788 KB Output is correct
97 Correct 4748 ms 376748 KB Output is correct
98 Correct 4649 ms 376660 KB Output is correct
99 Correct 4608 ms 376796 KB Output is correct
100 Correct 4577 ms 376920 KB Output is correct