oj.uz

Submission #538451

# Submission time Handle Problem Language Result Execution time Memory
538451 2022-03-17T01:47:28 Z schiftyfive4 Bridges (APIO19_bridges) C++17
100 / 100
 2288 ms 9576 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) "MJ >> LAMELO"
#endif

const int B = 800;

struct DSU {
  vector<int> f, siz, st;
  DSU(int n) : f(n), siz(n, 1) {
    iota(f.begin(), f.end(), 0);
  }
  int find(int x) {
    while (x != f[x]) {
      // x = f[x] = f[f[x]];
      x = f[x];
    }
    return x;
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    if (siz[y] > siz[x]) {
      swap(x, y);
    }
    siz[x] += siz[y];
    f[y] = x;
    st.push_back(y);
    return true;
  }
  int size(int x) {
    return siz[find(x)];
  }
  void rollback() {
    if (!st.empty()) {
      int x = st.back();
      st.pop_back();
      siz[f[x]] -= siz[x];
      f[x] = x;
    }
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<array<int, 3>> e;
  for (int i = 0; i < m; i++) {
    int u, v, d;
    cin >> u >> v >> d;
    --u;
    --v;
    e.push_back({u, v, d});
  }
  int q;
  cin >> q;
  vector<array<int, 3>> Q(q);
  for (int i = 0; i < q; i++) {
    cin >> Q[i][0] >> Q[i][1] >> Q[i][2];
    Q[i][1]--;
  }
  vector<int> ans(q);
  for (int L = 0; L < q; L += B) {
    vector<int> mark(m);
    vector<int> same;
    vector<int> diff;
    vector<int> t2;
    int R = min(L + B, q);
    for (int i = L; i < R; i++) {
      if (Q[i][0] == 1) {
        mark[Q[i][1]] = 1;
        diff.push_back(Q[i][1]);
      } else {
        t2.push_back(i);
      }
    }
    vector<vector<int>> c(B);
    for (int i = L; i < R; i++) {
      if (Q[i][0] == 1) {
        e[Q[i][1]][2] = Q[i][2];
      } else {
        for (int j : diff) {
          if (e[j][2] >= Q[i][2]) {
            c[i - L].push_back(j);
          }
        }
      }
    }
    for (int i = 0; i < m; i++) {
      if (!mark[i]) {
        same.push_back(i);
      }
    }
    sort(t2.begin(), t2.end(), [&](int i, int j) {
      return Q[i][2] > Q[j][2];
    });
    sort(same.begin(), same.end(), [&](int i, int j) {
      return e[i][2] > e[j][2];
    });
    DSU d(n);
    int ptr = 0;
    for (int i : t2) {
      while (ptr < (int) same.size() && e[same[ptr]][2] >= Q[i][2]) {
        d.merge(e[same[ptr]][0], e[same[ptr]][1]);
        ptr++;
      }
      int cnt = 0;
      for (int j : c[i - L]) {
        if (d.merge(e[j][0], e[j][1])) {
          cnt++;
        }
      }
      ans[i] = d.size(Q[i][1]);
      while (cnt--) {
        d.rollback();
      }
    }
  }
  for (int i = 0; i < q; i++) {
    if (Q[i][0] == 2) {
      cout << ans[i] << '\n';
    }
  }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 33 ms 1152 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 26 ms 1108 KB Output is correct
6 Correct 20 ms 1160 KB Output is correct
7 Correct 25 ms 1100 KB Output is correct
8 Correct 30 ms 1104 KB Output is correct
9 Correct 28 ms 1416 KB Output is correct
10 Correct 33 ms 1132 KB Output is correct
11 Correct 31 ms 1052 KB Output is correct
12 Correct 39 ms 1288 KB Output is correct
13 Correct 39 ms 1108 KB Output is correct
14 Correct 33 ms 1108 KB Output is correct
15 Correct 37 ms 1164 KB Output is correct
16 Correct 30 ms 1224 KB Output is correct
17 Correct 31 ms 1224 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1494 ms 7344 KB Output is correct
2 Correct 1476 ms 7300 KB Output is correct
3 Correct 1454 ms 7144 KB Output is correct
4 Correct 1536 ms 7256 KB Output is correct
5 Correct 1503 ms 7272 KB Output is correct
6 Correct 2017 ms 7540 KB Output is correct
7 Correct 1997 ms 7344 KB Output is correct
8 Correct 2033 ms 7468 KB Output is correct
9 Correct 35 ms 3396 KB Output is correct
10 Correct 1092 ms 6108 KB Output is correct
11 Correct 1012 ms 6392 KB Output is correct
12 Correct 1310 ms 6788 KB Output is correct
13 Correct 1326 ms 7044 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1121 ms 6032 KB Output is correct
2 Correct 705 ms 4636 KB Output is correct
3 Correct 1281 ms 6056 KB Output is correct
4 Correct 1077 ms 6200 KB Output is correct
5 Correct 36 ms 3404 KB Output is correct
6 Correct 1225 ms 6184 KB Output is correct
7 Correct 1022 ms 5928 KB Output is correct
8 Correct 918 ms 5804 KB Output is correct
9 Correct 776 ms 5892 KB Output is correct
10 Correct 726 ms 5708 KB Output is correct
11 Correct 808 ms 5688 KB Output is correct
12 Correct 728 ms 5592 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1993 ms 8956 KB Output is correct
2 Correct 35 ms 3408 KB Output is correct
3 Correct 187 ms 4820 KB Output is correct
4 Correct 88 ms 4924 KB Output is correct
5 Correct 984 ms 7320 KB Output is correct
6 Correct 1838 ms 8832 KB Output is correct
7 Correct 982 ms 7188 KB Output is correct
8 Correct 941 ms 6556 KB Output is correct
9 Correct 947 ms 6864 KB Output is correct
10 Correct 950 ms 6400 KB Output is correct
11 Correct 1407 ms 7812 KB Output is correct
12 Correct 1403 ms 7772 KB Output is correct
13 Correct 1423 ms 7576 KB Output is correct
14 Correct 845 ms 7292 KB Output is correct
15 Correct 905 ms 7292 KB Output is correct
16 Correct 1864 ms 9020 KB Output is correct
17 Correct 1895 ms 8764 KB Output is correct
18 Correct 1843 ms 8844 KB Output is correct
19 Correct 1856 ms 8772 KB Output is correct
20 Correct 1581 ms 7768 KB Output is correct
21 Correct 1584 ms 7756 KB Output is correct
22 Correct 1775 ms 8160 KB Output is correct
23 Correct 1042 ms 6604 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1494 ms 7344 KB Output is correct
2 Correct 1476 ms 7300 KB Output is correct
3 Correct 1454 ms 7144 KB Output is correct
4 Correct 1536 ms 7256 KB Output is correct
5 Correct 1503 ms 7272 KB Output is correct
6 Correct 2017 ms 7540 KB Output is correct
7 Correct 1997 ms 7344 KB Output is correct
8 Correct 2033 ms 7468 KB Output is correct
9 Correct 35 ms 3396 KB Output is correct
10 Correct 1092 ms 6108 KB Output is correct
11 Correct 1012 ms 6392 KB Output is correct
12 Correct 1310 ms 6788 KB Output is correct
13 Correct 1326 ms 7044 KB Output is correct
14 Correct 1121 ms 6032 KB Output is correct
15 Correct 705 ms 4636 KB Output is correct
16 Correct 1281 ms 6056 KB Output is correct
17 Correct 1077 ms 6200 KB Output is correct
18 Correct 36 ms 3404 KB Output is correct
19 Correct 1225 ms 6184 KB Output is correct
20 Correct 1022 ms 5928 KB Output is correct
21 Correct 918 ms 5804 KB Output is correct
22 Correct 776 ms 5892 KB Output is correct
23 Correct 726 ms 5708 KB Output is correct
24 Correct 808 ms 5688 KB Output is correct
25 Correct 728 ms 5592 KB Output is correct
26 Correct 1413 ms 7044 KB Output is correct
27 Correct 1700 ms 7204 KB Output is correct
28 Correct 1495 ms 7332 KB Output is correct
29 Correct 1142 ms 6840 KB Output is correct
30 Correct 1639 ms 7336 KB Output is correct
31 Correct 1747 ms 7112 KB Output is correct
32 Correct 1801 ms 7148 KB Output is correct
33 Correct 1624 ms 7088 KB Output is correct
34 Correct 1624 ms 7072 KB Output is correct
35 Correct 1492 ms 7204 KB Output is correct
36 Correct 1203 ms 6912 KB Output is correct
37 Correct 1242 ms 6820 KB Output is correct
38 Correct 1208 ms 6988 KB Output is correct
39 Correct 1061 ms 6776 KB Output is correct
40 Correct 1022 ms 6752 KB Output is correct
41 Correct 1072 ms 6684 KB Output is correct
42 Correct 999 ms 6716 KB Output is correct
43 Correct 1020 ms 6692 KB Output is correct
44 Correct 1004 ms 6672 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 33 ms 1152 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 26 ms 1108 KB Output is correct
6 Correct 20 ms 1160 KB Output is correct
7 Correct 25 ms 1100 KB Output is correct
8 Correct 30 ms 1104 KB Output is correct
9 Correct 28 ms 1416 KB Output is correct
10 Correct 33 ms 1132 KB Output is correct
11 Correct 31 ms 1052 KB Output is correct
12 Correct 39 ms 1288 KB Output is correct
13 Correct 39 ms 1108 KB Output is correct
14 Correct 33 ms 1108 KB Output is correct
15 Correct 37 ms 1164 KB Output is correct
16 Correct 30 ms 1224 KB Output is correct
17 Correct 31 ms 1224 KB Output is correct
18 Correct 1494 ms 7344 KB Output is correct
19 Correct 1476 ms 7300 KB Output is correct
20 Correct 1454 ms 7144 KB Output is correct
21 Correct 1536 ms 7256 KB Output is correct
22 Correct 1503 ms 7272 KB Output is correct
23 Correct 2017 ms 7540 KB Output is correct
24 Correct 1997 ms 7344 KB Output is correct
25 Correct 2033 ms 7468 KB Output is correct
26 Correct 35 ms 3396 KB Output is correct
27 Correct 1092 ms 6108 KB Output is correct
28 Correct 1012 ms 6392 KB Output is correct
29 Correct 1310 ms 6788 KB Output is correct
30 Correct 1326 ms 7044 KB Output is correct
31 Correct 1121 ms 6032 KB Output is correct
32 Correct 705 ms 4636 KB Output is correct
33 Correct 1281 ms 6056 KB Output is correct
34 Correct 1077 ms 6200 KB Output is correct
35 Correct 36 ms 3404 KB Output is correct
36 Correct 1225 ms 6184 KB Output is correct
37 Correct 1022 ms 5928 KB Output is correct
38 Correct 918 ms 5804 KB Output is correct
39 Correct 776 ms 5892 KB Output is correct
40 Correct 726 ms 5708 KB Output is correct
41 Correct 808 ms 5688 KB Output is correct
42 Correct 728 ms 5592 KB Output is correct
43 Correct 1993 ms 8956 KB Output is correct
44 Correct 35 ms 3408 KB Output is correct
45 Correct 187 ms 4820 KB Output is correct
46 Correct 88 ms 4924 KB Output is correct
47 Correct 984 ms 7320 KB Output is correct
48 Correct 1838 ms 8832 KB Output is correct
49 Correct 982 ms 7188 KB Output is correct
50 Correct 941 ms 6556 KB Output is correct
51 Correct 947 ms 6864 KB Output is correct
52 Correct 950 ms 6400 KB Output is correct
53 Correct 1407 ms 7812 KB Output is correct
54 Correct 1403 ms 7772 KB Output is correct
55 Correct 1423 ms 7576 KB Output is correct
56 Correct 845 ms 7292 KB Output is correct
57 Correct 905 ms 7292 KB Output is correct
58 Correct 1864 ms 9020 KB Output is correct
59 Correct 1895 ms 8764 KB Output is correct
60 Correct 1843 ms 8844 KB Output is correct
61 Correct 1856 ms 8772 KB Output is correct
62 Correct 1581 ms 7768 KB Output is correct
63 Correct 1584 ms 7756 KB Output is correct
64 Correct 1775 ms 8160 KB Output is correct
65 Correct 1042 ms 6604 KB Output is correct
66 Correct 1413 ms 7044 KB Output is correct
67 Correct 1700 ms 7204 KB Output is correct
68 Correct 1495 ms 7332 KB Output is correct
69 Correct 1142 ms 6840 KB Output is correct
70 Correct 1639 ms 7336 KB Output is correct
71 Correct 1747 ms 7112 KB Output is correct
72 Correct 1801 ms 7148 KB Output is correct
73 Correct 1624 ms 7088 KB Output is correct
74 Correct 1624 ms 7072 KB Output is correct
75 Correct 1492 ms 7204 KB Output is correct
76 Correct 1203 ms 6912 KB Output is correct
77 Correct 1242 ms 6820 KB Output is correct
78 Correct 1208 ms 6988 KB Output is correct
79 Correct 1061 ms 6776 KB Output is correct
80 Correct 1022 ms 6752 KB Output is correct
81 Correct 1072 ms 6684 KB Output is correct
82 Correct 999 ms 6716 KB Output is correct
83 Correct 1020 ms 6692 KB Output is correct
84 Correct 1004 ms 6672 KB Output is correct
85 Correct 2252 ms 9256 KB Output is correct
86 Correct 212 ms 5308 KB Output is correct
87 Correct 112 ms 5780 KB Output is correct
88 Correct 1278 ms 7792 KB Output is correct
89 Correct 2192 ms 9264 KB Output is correct
90 Correct 1273 ms 7776 KB Output is correct
91 Correct 1532 ms 7088 KB Output is correct
92 Correct 1508 ms 7344 KB Output is correct
93 Correct 2027 ms 7572 KB Output is correct
94 Correct 1852 ms 8100 KB Output is correct
95 Correct 1860 ms 8192 KB Output is correct
96 Correct 2004 ms 8540 KB Output is correct
97 Correct 1074 ms 7504 KB Output is correct
98 Correct 1128 ms 7388 KB Output is correct
99 Correct 2240 ms 9316 KB Output is correct
100 Correct 2243 ms 9388 KB Output is correct
101 Correct 2285 ms 9356 KB Output is correct
102 Correct 2288 ms 9328 KB Output is correct
103 Correct 2198 ms 8736 KB Output is correct
104 Correct 2169 ms 8720 KB Output is correct
105 Correct 1823 ms 8568 KB Output is correct
106 Correct 1528 ms 7856 KB Output is correct
107 Correct 1714 ms 8644 KB Output is correct
108 Correct 2162 ms 9576 KB Output is correct
109 Correct 1439 ms 7288 KB Output is correct