oj.uz

Submission #470051

# Submission time Handle Problem Language Result Execution time Memory
470051 2021-09-02T19:06:17 Z flashmt Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 4093 ms 260028 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;

struct Edge
{
  int x, y;
  long long c;
};

struct SegmentTree
{
  int low, mid, high;
  long long v, save;
  SegmentTree *l, *r;

  SegmentTree(int low, int high, long long initialDist[]): low(low), high(high)
  {
    mid = (low + high) / 2;
    save = 0;
    if (low == high) v = initialDist[low];
    else
    {
      l = new SegmentTree(low, mid, initialDist);
      r = new SegmentTree(mid + 1, high, initialDist);
      v = max(l->v, r->v);
    }
  }

  void pushDown()
  {
    l->v += save;
    l->save += save;
    r->v += save;
    r->save += save;
    save = 0;
  }

  void update(int x, int y, long long dif)
  {
    if (low == x && high == y)
    {
      v += dif;
      save += dif;
    }
    else
    {
      pushDown();
      if (x <= mid)
        l->update(x, min(y, mid), dif);
      if (mid < y)
        r->update(max(x, mid + 1), y, dif);
      v = max(l->v, r->v);
    }
  }

  long long get(int x, int y)
  {
    if (low == x && high == y)
      return v;
    pushDown();
    long long u = 0, v = 0;
    if (x <= mid)
      u = l->get(x, min(y, mid));
    if (mid < y)
      v = r->get(max(x, mid + 1), y);
    return max(u, v);
  }
};

struct CentroidData
{
  SegmentTree *segTree;
  multiset<long long> candidates;
  vector<pair<int, int>> segments;

  long long getAns()
  {
    if (candidates.empty())
      return 0;
    auto u = candidates.rbegin();
    return candidates.size() == 1 ? *u : *u + *(++u);
  }
};

struct CentroidNode
{
  int root, preDfs, postDfs, branchId;
};

int n, dfsTime;
Edge edges[N];
vector<pair<int, int>> adj[N];
long long initialDist[N];
multiset<long long> ans;
// centroid variables
int done[N], treeSize[N];
vector<int> activeNodes;
CentroidData centroidData[N];
vector<CentroidNode> centroidNodes[N];

void dfsPre(int x, int par, long long dist, int root, int branchId)
{
  int preDfs = ++dfsTime;
  initialDist[preDfs] = dist;
  for (auto u : adj[x])
  {
    int y = u.first;
    if (y != par && !done[y])
      dfsPre(y, x, dist + edges[u.second].c, root, branchId);
  }
  centroidNodes[x].push_back({root, preDfs, dfsTime, branchId});
}

void initCentroid(int root)
{
  int branchId = 0;
  dfsTime = 0;
  for (auto u : adj[root])
  {
    int x = u.first;
    if (!done[x])
    {
      dfsPre(x, root, edges[u.second].c, root, branchId);
      CentroidNode node = centroidNodes[x].back();
      centroidData[root].segments.push_back({node.preDfs, node.postDfs});
      branchId++;
    }
  }

  centroidNodes[root].push_back({root, 0, dfsTime, -1});
  centroidData[root].segTree = dfsTime > 0 ? new SegmentTree(1, dfsTime, initialDist) : NULL;
  for (auto u : centroidData[root].segments)
    centroidData[root].candidates.insert(centroidData[root].segTree->get(u.first, u.second));
  ans.insert(centroidData[root].getAns());
}

void dfs(int x, int par)
{
  activeNodes.push_back(x);
  treeSize[x] = 1;
  for (auto u : adj[x])
  {
    int y = u.first;
    if (!done[y] && y != par)
    {
      dfs(y, x);
      treeSize[x] += treeSize[y];
    }
  }
}

void decompose(int x)
{
  activeNodes.clear();
  dfs(x, 0);
  int centroid = x;
  for (int y : activeNodes)
    if (treeSize[y] * 2 >= treeSize[x] && treeSize[y] < treeSize[centroid])
      centroid = y;

  initCentroid(centroid);
  done[centroid] = 1;

  for (auto u : adj[centroid])
    if (!done[u.first])
      decompose(u.first);
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  long long w, e;
  int q, x, y, d;
  long long c;
  cin >> n >> q >> w;
  for (int i = 0; i < n - 1; i++)
  {
    cin >> x >> y >> c;
    adj[x].push_back({y, i});
    adj[y].push_back({x, i});
    edges[i] = {x, y, c};
  }

  decompose(1);

  long long curAns = 0;
  while (q--)
  {
    cin >> d >> e;
    int i = (d + curAns) % (n - 1), x = edges[i].x, y = edges[i].y;
    long long newC = (e + curAns) % w, diff = newC - edges[i].c;
    edges[i].c = newC;
    for (int j = 0; j < centroidNodes[x].size() && j < centroidNodes[y].size(); j++)
    {
      auto nodeX = centroidNodes[x][j], nodeY = centroidNodes[y][j];
      if (nodeX.root != nodeY.root)
        break;

      int root = centroidNodes[x][j].root;
      if (nodeX.preDfs > nodeY.preDfs)
        swap(nodeX, nodeY);

      ans.erase(ans.find(centroidData[root].getAns()));
      auto segment = centroidData[root].segments[nodeY.branchId];
      auto &segTree = centroidData[root].segTree;
      auto &candidates = centroidData[root].candidates;
      long long u = segTree->get(segment.first, segment.second);
      candidates.erase(candidates.find(u));
      segTree->update(nodeY.preDfs, nodeY.postDfs, diff);
      candidates.insert(segTree->get(segment.first, segment.second));
      ans.insert(centroidData[root].getAns());
    }
    curAns = *ans.rbegin();
    cout << curAns << '\n';
  }
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:196:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CentroidNode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |     for (int j = 0; j < centroidNodes[x].size() && j < centroidNodes[y].size(); j++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:196:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<CentroidNode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |     for (int j = 0; j < centroidNodes[x].size() && j < centroidNodes[y].size(); j++)
      |                                                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12748 KB Output is correct
2 Correct 7 ms 12868 KB Output is correct
3 Correct 8 ms 12860 KB Output is correct
4 Correct 8 ms 12876 KB Output is correct
5 Correct 9 ms 12864 KB Output is correct
6 Correct 7 ms 12748 KB Output is correct
7 Correct 7 ms 12896 KB Output is correct
8 Correct 7 ms 12792 KB Output is correct
9 Correct 7 ms 12864 KB Output is correct
10 Correct 8 ms 12804 KB Output is correct
11 Correct 7 ms 12860 KB Output is correct
12 Correct 9 ms 12836 KB Output is correct
13 Correct 7 ms 12844 KB Output is correct
14 Correct 7 ms 12876 KB Output is correct
15 Correct 8 ms 12868 KB Output is correct
16 Correct 9 ms 12876 KB Output is correct
17 Correct 8 ms 12876 KB Output is correct
18 Correct 7 ms 12940 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12748 KB Output is correct
2 Correct 7 ms 12868 KB Output is correct
3 Correct 8 ms 12860 KB Output is correct
4 Correct 8 ms 12876 KB Output is correct
5 Correct 9 ms 12864 KB Output is correct
6 Correct 7 ms 12748 KB Output is correct
7 Correct 7 ms 12896 KB Output is correct
8 Correct 7 ms 12792 KB Output is correct
9 Correct 7 ms 12864 KB Output is correct
10 Correct 8 ms 12804 KB Output is correct
11 Correct 7 ms 12860 KB Output is correct
12 Correct 9 ms 12836 KB Output is correct
13 Correct 7 ms 12844 KB Output is correct
14 Correct 7 ms 12876 KB Output is correct
15 Correct 8 ms 12868 KB Output is correct
16 Correct 9 ms 12876 KB Output is correct
17 Correct 8 ms 12876 KB Output is correct
18 Correct 7 ms 12940 KB Output is correct
19 Correct 27 ms 13772 KB Output is correct
20 Correct 29 ms 13932 KB Output is correct
21 Correct 33 ms 14120 KB Output is correct
22 Correct 34 ms 14396 KB Output is correct
23 Correct 49 ms 18148 KB Output is correct
24 Correct 67 ms 19776 KB Output is correct
25 Correct 68 ms 20604 KB Output is correct
26 Correct 69 ms 21828 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12876 KB Output is correct
2 Correct 7 ms 12876 KB Output is correct
3 Correct 9 ms 12904 KB Output is correct
4 Correct 21 ms 13072 KB Output is correct
5 Correct 81 ms 13936 KB Output is correct
6 Correct 8 ms 12756 KB Output is correct
7 Correct 9 ms 13004 KB Output is correct
8 Correct 8 ms 13004 KB Output is correct
9 Correct 10 ms 13008 KB Output is correct
10 Correct 27 ms 13260 KB Output is correct
11 Correct 103 ms 14380 KB Output is correct
12 Correct 13 ms 14668 KB Output is correct
13 Correct 14 ms 14668 KB Output is correct
14 Correct 16 ms 14668 KB Output is correct
15 Correct 42 ms 14980 KB Output is correct
16 Correct 153 ms 16068 KB Output is correct
17 Correct 165 ms 48824 KB Output is correct
18 Correct 179 ms 48920 KB Output is correct
19 Correct 159 ms 48952 KB Output is correct
20 Correct 204 ms 49268 KB Output is correct
21 Correct 505 ms 50592 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14028 KB Output is correct
2 Correct 37 ms 14252 KB Output is correct
3 Correct 146 ms 14796 KB Output is correct
4 Correct 280 ms 15740 KB Output is correct
5 Correct 43 ms 30224 KB Output is correct
6 Correct 107 ms 30436 KB Output is correct
7 Correct 310 ms 30908 KB Output is correct
8 Correct 652 ms 31868 KB Output is correct
9 Correct 198 ms 114760 KB Output is correct
10 Correct 285 ms 114888 KB Output is correct
11 Correct 658 ms 115656 KB Output is correct
12 Correct 1181 ms 116580 KB Output is correct
13 Correct 406 ms 229440 KB Output is correct
14 Correct 537 ms 229504 KB Output is correct
15 Correct 1049 ms 230160 KB Output is correct
16 Correct 1768 ms 230916 KB Output is correct
17 Correct 3318 ms 231000 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3109 ms 183456 KB Output is correct
2 Correct 3208 ms 188684 KB Output is correct
3 Correct 3069 ms 187304 KB Output is correct
4 Correct 3170 ms 188752 KB Output is correct
5 Correct 3069 ms 178148 KB Output is correct
6 Correct 2676 ms 131468 KB Output is correct
7 Correct 4042 ms 234652 KB Output is correct
8 Correct 3986 ms 234672 KB Output is correct
9 Correct 4093 ms 234876 KB Output is correct
10 Correct 3968 ms 233728 KB Output is correct
11 Correct 3906 ms 221312 KB Output is correct
12 Correct 3370 ms 157360 KB Output is correct
13 Correct 3686 ms 259940 KB Output is correct
14 Correct 3748 ms 259980 KB Output is correct
15 Correct 3787 ms 259880 KB Output is correct
16 Correct 3739 ms 258720 KB Output is correct
17 Correct 3643 ms 243512 KB Output is correct
18 Correct 3028 ms 166800 KB Output is correct
19 Correct 3690 ms 259900 KB Output is correct
20 Correct 3654 ms 259908 KB Output is correct
21 Correct 3659 ms 260028 KB Output is correct
22 Correct 3634 ms 258708 KB Output is correct
23 Correct 3504 ms 243452 KB Output is correct
24 Correct 2831 ms 166868 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12748 KB Output is correct
2 Correct 7 ms 12868 KB Output is correct
3 Correct 8 ms 12860 KB Output is correct
4 Correct 8 ms 12876 KB Output is correct
5 Correct 9 ms 12864 KB Output is correct
6 Correct 7 ms 12748 KB Output is correct
7 Correct 7 ms 12896 KB Output is correct
8 Correct 7 ms 12792 KB Output is correct
9 Correct 7 ms 12864 KB Output is correct
10 Correct 8 ms 12804 KB Output is correct
11 Correct 7 ms 12860 KB Output is correct
12 Correct 9 ms 12836 KB Output is correct
13 Correct 7 ms 12844 KB Output is correct
14 Correct 7 ms 12876 KB Output is correct
15 Correct 8 ms 12868 KB Output is correct
16 Correct 9 ms 12876 KB Output is correct
17 Correct 8 ms 12876 KB Output is correct
18 Correct 7 ms 12940 KB Output is correct
19 Correct 27 ms 13772 KB Output is correct
20 Correct 29 ms 13932 KB Output is correct
21 Correct 33 ms 14120 KB Output is correct
22 Correct 34 ms 14396 KB Output is correct
23 Correct 49 ms 18148 KB Output is correct
24 Correct 67 ms 19776 KB Output is correct
25 Correct 68 ms 20604 KB Output is correct
26 Correct 69 ms 21828 KB Output is correct
27 Correct 7 ms 12876 KB Output is correct
28 Correct 7 ms 12876 KB Output is correct
29 Correct 9 ms 12904 KB Output is correct
30 Correct 21 ms 13072 KB Output is correct
31 Correct 81 ms 13936 KB Output is correct
32 Correct 8 ms 12756 KB Output is correct
33 Correct 9 ms 13004 KB Output is correct
34 Correct 8 ms 13004 KB Output is correct
35 Correct 10 ms 13008 KB Output is correct
36 Correct 27 ms 13260 KB Output is correct
37 Correct 103 ms 14380 KB Output is correct
38 Correct 13 ms 14668 KB Output is correct
39 Correct 14 ms 14668 KB Output is correct
40 Correct 16 ms 14668 KB Output is correct
41 Correct 42 ms 14980 KB Output is correct
42 Correct 153 ms 16068 KB Output is correct
43 Correct 165 ms 48824 KB Output is correct
44 Correct 179 ms 48920 KB Output is correct
45 Correct 159 ms 48952 KB Output is correct
46 Correct 204 ms 49268 KB Output is correct
47 Correct 505 ms 50592 KB Output is correct
48 Correct 12 ms 14028 KB Output is correct
49 Correct 37 ms 14252 KB Output is correct
50 Correct 146 ms 14796 KB Output is correct
51 Correct 280 ms 15740 KB Output is correct
52 Correct 43 ms 30224 KB Output is correct
53 Correct 107 ms 30436 KB Output is correct
54 Correct 310 ms 30908 KB Output is correct
55 Correct 652 ms 31868 KB Output is correct
56 Correct 198 ms 114760 KB Output is correct
57 Correct 285 ms 114888 KB Output is correct
58 Correct 658 ms 115656 KB Output is correct
59 Correct 1181 ms 116580 KB Output is correct
60 Correct 406 ms 229440 KB Output is correct
61 Correct 537 ms 229504 KB Output is correct
62 Correct 1049 ms 230160 KB Output is correct
63 Correct 1768 ms 230916 KB Output is correct
64 Correct 3318 ms 231000 KB Output is correct
65 Correct 3109 ms 183456 KB Output is correct
66 Correct 3208 ms 188684 KB Output is correct
67 Correct 3069 ms 187304 KB Output is correct
68 Correct 3170 ms 188752 KB Output is correct
69 Correct 3069 ms 178148 KB Output is correct
70 Correct 2676 ms 131468 KB Output is correct
71 Correct 4042 ms 234652 KB Output is correct
72 Correct 3986 ms 234672 KB Output is correct
73 Correct 4093 ms 234876 KB Output is correct
74 Correct 3968 ms 233728 KB Output is correct
75 Correct 3906 ms 221312 KB Output is correct
76 Correct 3370 ms 157360 KB Output is correct
77 Correct 3686 ms 259940 KB Output is correct
78 Correct 3748 ms 259980 KB Output is correct
79 Correct 3787 ms 259880 KB Output is correct
80 Correct 3739 ms 258720 KB Output is correct
81 Correct 3643 ms 243512 KB Output is correct
82 Correct 3028 ms 166800 KB Output is correct
83 Correct 3690 ms 259900 KB Output is correct
84 Correct 3654 ms 259908 KB Output is correct
85 Correct 3659 ms 260028 KB Output is correct
86 Correct 3634 ms 258708 KB Output is correct
87 Correct 3504 ms 243452 KB Output is correct
88 Correct 2831 ms 166868 KB Output is correct
89 Correct 2958 ms 185060 KB Output is correct
90 Correct 3363 ms 203756 KB Output is correct
91 Correct 3745 ms 227708 KB Output is correct
92 Correct 3878 ms 233880 KB Output is correct
93 Correct 3803 ms 243080 KB Output is correct
94 Correct 3783 ms 249292 KB Output is correct
95 Correct 3556 ms 257672 KB Output is correct
96 Correct 3573 ms 257852 KB Output is correct
97 Correct 3546 ms 257732 KB Output is correct
98 Correct 3781 ms 259148 KB Output is correct
99 Correct 3695 ms 257796 KB Output is correct
100 Correct 3756 ms 257904 KB Output is correct