oj.uz

Submission #849238

# Submission time Handle Problem Language Result Execution time Memory
849238 2023-09-14T09:46:17 Z tch1cherin Bridges (APIO19_bridges) C++17
100 / 100
 2832 ms 15100 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

struct dsu {
  vector<int> parent, rank;
  vector<vector<pair<int*, int>>> changes;

  dsu(int size) : parent(size), rank(size, 1) {
    iota(parent.begin(), parent.end(), 0);
  }

  int get(int u) {
    return parent[u] == u ? u : get(parent[u]);
  }

  void unite(int u, int v) {
    u = get(u), v = get(v);
    changes.push_back({});
    if (u != v) {
      if (rank[u] < rank[v]) {
        swap(u, v);
      }
      changes.back().reserve(2);
      changes.back().push_back({&rank[u], rank[u]});
      changes.back().push_back({&parent[v], parent[v]});
      rank[u] += rank[v];
      parent[v] = u;
    }
  }

  void rollback() {
    for (auto &[x, y] : changes.back()) {
      *x = y; 
    }
    changes.pop_back();
  }
};

struct edge {
  int from, to;
  int weight;
};

bool operator>(edge a, edge b) {
  return a.weight > b.weight;
}

const int BLOCK = 1000;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<edge> edges(M);
  for (auto &[from, to, weight] : edges) {
    cin >> from >> to >> weight;
    from--, to--;
  }
  int Q;
  cin >> Q;
  vector<int> answer(Q, -1);
  vector<tuple<int, int, int>> changes, queries;
  vector<bool> is_changed(M), used(M);
  for (int i = 0; i < Q; i++) {
    int T;
    cin >> T;
    if (T == 1) {
      int B, R;
      cin >> B >> R;
      B--;
      is_changed[B] = true;
      changes.push_back({i, B, R}); 
    } else {
      int S, W;
      cin >> S >> W;
      S--;
      queries.push_back({i, S, W});
    }
    if ((Q - i - 1) % BLOCK == 0) {
      vector<pair<edge, int>> sorted_edges(M);
      for (int i = 0; i < M; i++) {
        sorted_edges[i] = {edges[i], i};
      }
      sort(sorted_edges.begin(), sorted_edges.end(),
          [](pair<edge, int>& a, pair<edge, int>& b) {
        return a.first > b.first;
      });
      sort(queries.begin(), queries.end(),
          [](tuple<int, int, int> a, tuple<int, int, int> b) {
        return get<2>(a) > get<2>(b);
      });
      int ptr = 0;
      dsu sets(N);
      for (auto [j, S, W] : queries) {
        while (ptr < M && sorted_edges[ptr].first.weight >= W) {
          if (!is_changed[sorted_edges[ptr].second]) {
            sets.unite(sorted_edges[ptr].first.from, sorted_edges[ptr].first.to);
          }
          ptr++;
        }
        int x = (int)changes.size(); 
        for (int k = 0; k < (int)changes.size(); k++) {
          if (get<0>(changes[k]) > j) {
            x = k;
            break;
          }
        }
        int rollbacks = 0;
        for (int k = x - 1; k >= 0; k--) {
          if (!used[get<1>(changes[k])] && get<2>(changes[k]) >= W) {
            auto [from, to, weight] = edges[get<1>(changes[k])];
            sets.unite(from, to);
            rollbacks++;
          }
          used[get<1>(changes[k])] = true;
        }
        for (int k = (int)changes.size() - 1; k >= x; k--) {
          auto [y, B, R] = changes[k];
          if (!used[B] && edges[B].weight >= W) {
            used[B] = true;
            sets.unite(edges[B].from, edges[B].to);
            rollbacks++;
          }
        }
        answer[j] = sets.rank[sets.get(S)];
        for (int k = (int)changes.size() - 1; k >= 0; k--) {
          used[get<1>(changes[k])] = false;
        }
        for (int k = 0; k < rollbacks; k++) {
          sets.rollback();
        }
      }
      for (auto [j, B, R] : changes) {
        is_changed[B] = false;
        edges[B].weight = R;
      }
      vector<tuple<int, int, int>>().swap(changes);
      vector<tuple<int, int, int>>().swap(queries);
    }
  }
  for (int i = 0; i < Q; i++) {
    if (answer[i] != -1) {
      cout << answer[i] << "\n";
    }
  }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 33 ms 596 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 21 ms 348 KB Output is correct
6 Correct 20 ms 344 KB Output is correct
7 Correct 33 ms 348 KB Output is correct
8 Correct 24 ms 536 KB Output is correct
9 Correct 27 ms 348 KB Output is correct
10 Correct 25 ms 348 KB Output is correct
11 Correct 24 ms 540 KB Output is correct
12 Correct 27 ms 536 KB Output is correct
13 Correct 33 ms 532 KB Output is correct
14 Correct 29 ms 348 KB Output is correct
15 Correct 26 ms 544 KB Output is correct
16 Correct 26 ms 532 KB Output is correct
17 Correct 25 ms 520 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1702 ms 6612 KB Output is correct
2 Correct 1736 ms 6756 KB Output is correct
3 Correct 1780 ms 6620 KB Output is correct
4 Correct 1860 ms 6600 KB Output is correct
5 Correct 1821 ms 6612 KB Output is correct
6 Correct 2759 ms 6876 KB Output is correct
7 Correct 2769 ms 7112 KB Output is correct
8 Correct 2832 ms 7292 KB Output is correct
9 Correct 32 ms 860 KB Output is correct
10 Correct 1886 ms 6708 KB Output is correct
11 Correct 1763 ms 7012 KB Output is correct
12 Correct 1539 ms 8088 KB Output is correct
13 Correct 1664 ms 7868 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1284 ms 4604 KB Output is correct
2 Correct 1012 ms 1952 KB Output is correct
3 Correct 1541 ms 4792 KB Output is correct
4 Correct 1327 ms 4844 KB Output is correct
5 Correct 39 ms 860 KB Output is correct
6 Correct 1447 ms 4444 KB Output is correct
7 Correct 1188 ms 4376 KB Output is correct
8 Correct 1056 ms 4328 KB Output is correct
9 Correct 895 ms 4608 KB Output is correct
10 Correct 828 ms 4548 KB Output is correct
11 Correct 924 ms 4328 KB Output is correct
12 Correct 829 ms 4320 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2004 ms 10416 KB Output is correct
2 Correct 38 ms 2380 KB Output is correct
3 Correct 190 ms 11000 KB Output is correct
4 Correct 162 ms 11164 KB Output is correct
5 Correct 1840 ms 12428 KB Output is correct
6 Correct 2013 ms 14000 KB Output is correct
7 Correct 1790 ms 12912 KB Output is correct
8 Correct 1099 ms 9080 KB Output is correct
9 Correct 1093 ms 8944 KB Output is correct
10 Correct 1100 ms 8788 KB Output is correct
11 Correct 1620 ms 12192 KB Output is correct
12 Correct 1614 ms 12432 KB Output is correct
13 Correct 1630 ms 12040 KB Output is correct
14 Correct 1761 ms 13412 KB Output is correct
15 Correct 1832 ms 12704 KB Output is correct
16 Correct 2055 ms 14660 KB Output is correct
17 Correct 2136 ms 13780 KB Output is correct
18 Correct 2127 ms 14044 KB Output is correct
19 Correct 2123 ms 13856 KB Output is correct
20 Correct 1879 ms 12464 KB Output is correct
21 Correct 1860 ms 12736 KB Output is correct
22 Correct 2060 ms 13376 KB Output is correct
23 Correct 1571 ms 11272 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1702 ms 6612 KB Output is correct
2 Correct 1736 ms 6756 KB Output is correct
3 Correct 1780 ms 6620 KB Output is correct
4 Correct 1860 ms 6600 KB Output is correct
5 Correct 1821 ms 6612 KB Output is correct
6 Correct 2759 ms 6876 KB Output is correct
7 Correct 2769 ms 7112 KB Output is correct
8 Correct 2832 ms 7292 KB Output is correct
9 Correct 32 ms 860 KB Output is correct
10 Correct 1886 ms 6708 KB Output is correct
11 Correct 1763 ms 7012 KB Output is correct
12 Correct 1539 ms 8088 KB Output is correct
13 Correct 1664 ms 7868 KB Output is correct
14 Correct 1284 ms 4604 KB Output is correct
15 Correct 1012 ms 1952 KB Output is correct
16 Correct 1541 ms 4792 KB Output is correct
17 Correct 1327 ms 4844 KB Output is correct
18 Correct 39 ms 860 KB Output is correct
19 Correct 1447 ms 4444 KB Output is correct
20 Correct 1188 ms 4376 KB Output is correct
21 Correct 1056 ms 4328 KB Output is correct
22 Correct 895 ms 4608 KB Output is correct
23 Correct 828 ms 4548 KB Output is correct
24 Correct 924 ms 4328 KB Output is correct
25 Correct 829 ms 4320 KB Output is correct
26 Correct 1759 ms 6544 KB Output is correct
27 Correct 2226 ms 7912 KB Output is correct
28 Correct 1792 ms 6560 KB Output is correct
29 Correct 1338 ms 6808 KB Output is correct
30 Correct 2016 ms 6524 KB Output is correct
31 Correct 2050 ms 7804 KB Output is correct
32 Correct 2063 ms 7896 KB Output is correct
33 Correct 1716 ms 6788 KB Output is correct
34 Correct 1745 ms 6516 KB Output is correct
35 Correct 1756 ms 6564 KB Output is correct
36 Correct 1349 ms 6808 KB Output is correct
37 Correct 1343 ms 6776 KB Output is correct
38 Correct 1327 ms 6776 KB Output is correct
39 Correct 1119 ms 6624 KB Output is correct
40 Correct 1122 ms 6772 KB Output is correct
41 Correct 1120 ms 6868 KB Output is correct
42 Correct 1116 ms 6972 KB Output is correct
43 Correct 1108 ms 6656 KB Output is correct
44 Correct 1105 ms 6608 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 33 ms 596 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 21 ms 348 KB Output is correct
6 Correct 20 ms 344 KB Output is correct
7 Correct 33 ms 348 KB Output is correct
8 Correct 24 ms 536 KB Output is correct
9 Correct 27 ms 348 KB Output is correct
10 Correct 25 ms 348 KB Output is correct
11 Correct 24 ms 540 KB Output is correct
12 Correct 27 ms 536 KB Output is correct
13 Correct 33 ms 532 KB Output is correct
14 Correct 29 ms 348 KB Output is correct
15 Correct 26 ms 544 KB Output is correct
16 Correct 26 ms 532 KB Output is correct
17 Correct 25 ms 520 KB Output is correct
18 Correct 1702 ms 6612 KB Output is correct
19 Correct 1736 ms 6756 KB Output is correct
20 Correct 1780 ms 6620 KB Output is correct
21 Correct 1860 ms 6600 KB Output is correct
22 Correct 1821 ms 6612 KB Output is correct
23 Correct 2759 ms 6876 KB Output is correct
24 Correct 2769 ms 7112 KB Output is correct
25 Correct 2832 ms 7292 KB Output is correct
26 Correct 32 ms 860 KB Output is correct
27 Correct 1886 ms 6708 KB Output is correct
28 Correct 1763 ms 7012 KB Output is correct
29 Correct 1539 ms 8088 KB Output is correct
30 Correct 1664 ms 7868 KB Output is correct
31 Correct 1284 ms 4604 KB Output is correct
32 Correct 1012 ms 1952 KB Output is correct
33 Correct 1541 ms 4792 KB Output is correct
34 Correct 1327 ms 4844 KB Output is correct
35 Correct 39 ms 860 KB Output is correct
36 Correct 1447 ms 4444 KB Output is correct
37 Correct 1188 ms 4376 KB Output is correct
38 Correct 1056 ms 4328 KB Output is correct
39 Correct 895 ms 4608 KB Output is correct
40 Correct 828 ms 4548 KB Output is correct
41 Correct 924 ms 4328 KB Output is correct
42 Correct 829 ms 4320 KB Output is correct
43 Correct 2004 ms 10416 KB Output is correct
44 Correct 38 ms 2380 KB Output is correct
45 Correct 190 ms 11000 KB Output is correct
46 Correct 162 ms 11164 KB Output is correct
47 Correct 1840 ms 12428 KB Output is correct
48 Correct 2013 ms 14000 KB Output is correct
49 Correct 1790 ms 12912 KB Output is correct
50 Correct 1099 ms 9080 KB Output is correct
51 Correct 1093 ms 8944 KB Output is correct
52 Correct 1100 ms 8788 KB Output is correct
53 Correct 1620 ms 12192 KB Output is correct
54 Correct 1614 ms 12432 KB Output is correct
55 Correct 1630 ms 12040 KB Output is correct
56 Correct 1761 ms 13412 KB Output is correct
57 Correct 1832 ms 12704 KB Output is correct
58 Correct 2055 ms 14660 KB Output is correct
59 Correct 2136 ms 13780 KB Output is correct
60 Correct 2127 ms 14044 KB Output is correct
61 Correct 2123 ms 13856 KB Output is correct
62 Correct 1879 ms 12464 KB Output is correct
63 Correct 1860 ms 12736 KB Output is correct
64 Correct 2060 ms 13376 KB Output is correct
65 Correct 1571 ms 11272 KB Output is correct
66 Correct 1759 ms 6544 KB Output is correct
67 Correct 2226 ms 7912 KB Output is correct
68 Correct 1792 ms 6560 KB Output is correct
69 Correct 1338 ms 6808 KB Output is correct
70 Correct 2016 ms 6524 KB Output is correct
71 Correct 2050 ms 7804 KB Output is correct
72 Correct 2063 ms 7896 KB Output is correct
73 Correct 1716 ms 6788 KB Output is correct
74 Correct 1745 ms 6516 KB Output is correct
75 Correct 1756 ms 6564 KB Output is correct
76 Correct 1349 ms 6808 KB Output is correct
77 Correct 1343 ms 6776 KB Output is correct
78 Correct 1327 ms 6776 KB Output is correct
79 Correct 1119 ms 6624 KB Output is correct
80 Correct 1122 ms 6772 KB Output is correct
81 Correct 1120 ms 6868 KB Output is correct
82 Correct 1116 ms 6972 KB Output is correct
83 Correct 1108 ms 6656 KB Output is correct
84 Correct 1105 ms 6608 KB Output is correct
85 Correct 2322 ms 14048 KB Output is correct
86 Correct 226 ms 11192 KB Output is correct
87 Correct 182 ms 10984 KB Output is correct
88 Correct 1989 ms 13040 KB Output is correct
89 Correct 2311 ms 15100 KB Output is correct
90 Correct 2013 ms 13176 KB Output is correct
91 Correct 1810 ms 9228 KB Output is correct
92 Correct 1825 ms 9464 KB Output is correct
93 Correct 2632 ms 10128 KB Output is correct
94 Correct 1985 ms 12968 KB Output is correct
95 Correct 2047 ms 13508 KB Output is correct
96 Correct 1955 ms 13412 KB Output is correct
97 Correct 1809 ms 13328 KB Output is correct
98 Correct 1862 ms 13176 KB Output is correct
99 Correct 2483 ms 13896 KB Output is correct
100 Correct 2356 ms 14108 KB Output is correct
101 Correct 2537 ms 14312 KB Output is correct
102 Correct 2438 ms 14036 KB Output is correct
103 Correct 2242 ms 12404 KB Output is correct
104 Correct 2157 ms 12976 KB Output is correct
105 Correct 1838 ms 12804 KB Output is correct
106 Correct 1579 ms 12804 KB Output is correct
107 Correct 1910 ms 12340 KB Output is correct
108 Correct 2261 ms 14640 KB Output is correct
109 Correct 1736 ms 12188 KB Output is correct