Submission #284530

# Submission time Handle Problem Language Result Execution time Memory
284530 2020-08-27T14:59:51 Z WLZ Bridges (APIO19_bridges) C++14
100 / 100
2338 ms 16660 KB
#include <bits/stdc++.h>
using namespace std;
 
struct dsu {
  private: vector<int> p, sz;
  public:
    dsu(int n) {
      p.assign(n, -1);
      sz.assign(n, 1);
    }

    int root(int x) {
      if (p[x] < 0) {
        return x;
      }
      return (p[x] = root(p[x]));
    }

    bool same_set(int x, int y) {
      return (root(x) == root(y));
    }

    void connect(int x, int y) {
      x = root(x); y = root(y);
      if (x != y) {
        if (sz[x] > sz[y]) {
          p[y] = x;
          sz[x] += sz[y];
        } else {
          p[x] = y;
          sz[y] += sz[x];
        }
      }
    }

    int set_sz(int x) {
      return sz[root(x)];
    }
};

struct edge {
  int u, v, d, idx;
};

struct query {
  int type, x, y, idx;
};

vector<int> was;
vector< vector<int> > g;
dsu conn(0);
int cnt = 0;

int dfs(int u) {
  was[u] = cnt;
  int ans = conn.set_sz(u);
  for (auto& v : g[u]) {
    if (was[v] != cnt) {
      ans += dfs(v);
    }
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<edge> edges(m);
  vector<int> after(m);
  for (int i = 0; i < m; i++) {
    cin >> edges[i].u >> edges[i].v >> edges[i].d;
    edges[i].idx = i;
    after[i] = edges[i].d;
  }
  vector<edge> unsorted_edges(edges);
  int q;
  cin >> q;
  vector<query> queries(q);
  for (int i = 0; i < q; i++) {
    cin >> queries[i].type >> queries[i].x >> queries[i].y;
    queries[i].idx = i;
  }
  sort(edges.begin(), edges.end(), [](const edge &a, const edge &b) {
    return a.d > b.d;
  });
  const int k = floor(sqrt(q));
  vector<int> ans(q, -1);
  g.resize(n + 1);
  was.assign(n + 1, -1);
  for (int i = 0; i < q; i += k) {
    conn = dsu(n + 1);
    vector<query> q1, q2;
    vector<bool> use(m, true);
    for (int j = i; j < min(q, i + k); j++) {
      if (queries[j].type == 1) {
        q2.push_back(queries[j]);
        use[queries[j].x - 1] = false;
      } else {
        q1.push_back(queries[j]);
      }
    }
    sort(q1.begin(), q1.end(), [](const query &a, const query &b) {
      return a.y > b.y;
    });
    int ptr = 0;
    for (int j = 0; j < (int) q1.size(); j++) {
      while (ptr < m && edges[ptr].d >= q1[j].y) {
        if (use[edges[ptr].idx]) {
          conn.connect(edges[ptr].u, edges[ptr].v);
        }
        ptr++;
      }
      for (int t = 0; t < (int) q2.size(); t++) {
        if (q2[t].idx > q1[j].idx) {
          break;
        }
        after[q2[t].x - 1] = q2[t].y;
      }
      for (int t = 0; t < (int) q2.size(); t++) {
        if (after[q2[t].x - 1] >= q1[j].y) {
          int u = conn.root(unsorted_edges[q2[t].x - 1].u);
          int v = conn.root(unsorted_edges[q2[t].x - 1].v);
          g[u].push_back(v);
          g[v].push_back(u);
        }
      }
      ans[q1[j].idx] = dfs(conn.root(q1[j].x));
      cnt++;
      for (int t = 0; t < (int) q2.size(); t++) {
        if (after[q2[t].x - 1] >= q1[j].y) {
          int u = conn.root(unsorted_edges[q2[t].x - 1].u);
          int v = conn.root(unsorted_edges[q2[t].x - 1].v);
          g[u].clear();
          g[v].clear();
        }
        after[q2[t].x - 1] = unsorted_edges[q2[t].x - 1].d;
      }
    }
    vector<edge> changed, not_changed;
    for (int j = 0; j < (int) q2.size(); j++) {
      unsorted_edges[q2[j].x - 1].d = after[q2[j].x - 1] = q2[j].y;
    }
    for (int j = 0; j < m; j++) {
      if (use[edges[j].idx]) {
        not_changed.push_back(edges[j]);
      } else {
        changed.push_back(unsorted_edges[edges[j].idx]);
      }
    }
    sort(changed.begin(), changed.end(), [](const edge &a, const edge &b) {
      return a.d > b.d;
    });
    edges.clear();
    int j = 0, t = 0;
    while (j < (int) not_changed.size() || t < (int) changed.size()) {
      if (j == (int) not_changed.size()) {
        edges.push_back(changed[t++]);
      } else if (t == (int) changed.size()) {
        edges.push_back(not_changed[j++]);
      } else if (not_changed[j].d > changed[t].d) {
        edges.push_back(not_changed[j++]);
      } else {
        edges.push_back(changed[t++]);
      }
    }
  }
  for (int i = 0; i < q; i++) {
    if (ans[i] != -1) {
      cout << ans[i] << '\n';
    }
  }
  return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 16 ms 896 KB Output is correct
4 Correct 4 ms 768 KB Output is correct
5 Correct 14 ms 768 KB Output is correct
6 Correct 13 ms 768 KB Output is correct
7 Correct 14 ms 640 KB Output is correct
8 Correct 14 ms 768 KB Output is correct
9 Correct 17 ms 640 KB Output is correct
10 Correct 14 ms 768 KB Output is correct
11 Correct 13 ms 768 KB Output is correct
12 Correct 15 ms 768 KB Output is correct
13 Correct 16 ms 768 KB Output is correct
14 Correct 15 ms 768 KB Output is correct
15 Correct 17 ms 768 KB Output is correct
16 Correct 15 ms 640 KB Output is correct
17 Correct 24 ms 640 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1131 ms 11916 KB Output is correct
2 Correct 1091 ms 12124 KB Output is correct
3 Correct 1137 ms 12032 KB Output is correct
4 Correct 1103 ms 12256 KB Output is correct
5 Correct 1160 ms 12256 KB Output is correct
6 Correct 1417 ms 11060 KB Output is correct
7 Correct 1418 ms 10932 KB Output is correct
8 Correct 1368 ms 11264 KB Output is correct
9 Correct 39 ms 3832 KB Output is correct
10 Correct 1138 ms 10968 KB Output is correct
11 Correct 1109 ms 10900 KB Output is correct
12 Correct 828 ms 10904 KB Output is correct
13 Correct 984 ms 11092 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 842 ms 9212 KB Output is correct
2 Correct 658 ms 5468 KB Output is correct
3 Correct 996 ms 9228 KB Output is correct
4 Correct 908 ms 9156 KB Output is correct
5 Correct 39 ms 3832 KB Output is correct
6 Correct 940 ms 9020 KB Output is correct
7 Correct 780 ms 9164 KB Output is correct
8 Correct 712 ms 9404 KB Output is correct
9 Correct 576 ms 8928 KB Output is correct
10 Correct 531 ms 8696 KB Output is correct
11 Correct 622 ms 9104 KB Output is correct
12 Correct 570 ms 9336 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1739 ms 15672 KB Output is correct
2 Correct 53 ms 3960 KB Output is correct
3 Correct 377 ms 9756 KB Output is correct
4 Correct 356 ms 9816 KB Output is correct
5 Correct 1612 ms 14244 KB Output is correct
6 Correct 1700 ms 15656 KB Output is correct
7 Correct 1599 ms 14116 KB Output is correct
8 Correct 880 ms 10692 KB Output is correct
9 Correct 884 ms 10980 KB Output is correct
10 Correct 916 ms 10744 KB Output is correct
11 Correct 1643 ms 13564 KB Output is correct
12 Correct 1592 ms 13820 KB Output is correct
13 Correct 1580 ms 13708 KB Output is correct
14 Correct 1615 ms 14180 KB Output is correct
15 Correct 1626 ms 14404 KB Output is correct
16 Correct 1905 ms 15620 KB Output is correct
17 Correct 1901 ms 15804 KB Output is correct
18 Correct 1853 ms 15556 KB Output is correct
19 Correct 1856 ms 15676 KB Output is correct
20 Correct 1790 ms 14460 KB Output is correct
21 Correct 1744 ms 14352 KB Output is correct
22 Correct 1815 ms 15456 KB Output is correct
23 Correct 1580 ms 12916 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1131 ms 11916 KB Output is correct
2 Correct 1091 ms 12124 KB Output is correct
3 Correct 1137 ms 12032 KB Output is correct
4 Correct 1103 ms 12256 KB Output is correct
5 Correct 1160 ms 12256 KB Output is correct
6 Correct 1417 ms 11060 KB Output is correct
7 Correct 1418 ms 10932 KB Output is correct
8 Correct 1368 ms 11264 KB Output is correct
9 Correct 39 ms 3832 KB Output is correct
10 Correct 1138 ms 10968 KB Output is correct
11 Correct 1109 ms 10900 KB Output is correct
12 Correct 828 ms 10904 KB Output is correct
13 Correct 984 ms 11092 KB Output is correct
14 Correct 842 ms 9212 KB Output is correct
15 Correct 658 ms 5468 KB Output is correct
16 Correct 996 ms 9228 KB Output is correct
17 Correct 908 ms 9156 KB Output is correct
18 Correct 39 ms 3832 KB Output is correct
19 Correct 940 ms 9020 KB Output is correct
20 Correct 780 ms 9164 KB Output is correct
21 Correct 712 ms 9404 KB Output is correct
22 Correct 576 ms 8928 KB Output is correct
23 Correct 531 ms 8696 KB Output is correct
24 Correct 622 ms 9104 KB Output is correct
25 Correct 570 ms 9336 KB Output is correct
26 Correct 1099 ms 12020 KB Output is correct
27 Correct 1338 ms 12048 KB Output is correct
28 Correct 1157 ms 12192 KB Output is correct
29 Correct 925 ms 12032 KB Output is correct
30 Correct 1309 ms 11876 KB Output is correct
31 Correct 1289 ms 12292 KB Output is correct
32 Correct 1310 ms 12048 KB Output is correct
33 Correct 1146 ms 12392 KB Output is correct
34 Correct 1161 ms 12052 KB Output is correct
35 Correct 1087 ms 12220 KB Output is correct
36 Correct 972 ms 12044 KB Output is correct
37 Correct 971 ms 12224 KB Output is correct
38 Correct 995 ms 12100 KB Output is correct
39 Correct 840 ms 11504 KB Output is correct
40 Correct 826 ms 11336 KB Output is correct
41 Correct 827 ms 11452 KB Output is correct
42 Correct 820 ms 12208 KB Output is correct
43 Correct 723 ms 12088 KB Output is correct
44 Correct 761 ms 12036 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 16 ms 896 KB Output is correct
4 Correct 4 ms 768 KB Output is correct
5 Correct 14 ms 768 KB Output is correct
6 Correct 13 ms 768 KB Output is correct
7 Correct 14 ms 640 KB Output is correct
8 Correct 14 ms 768 KB Output is correct
9 Correct 17 ms 640 KB Output is correct
10 Correct 14 ms 768 KB Output is correct
11 Correct 13 ms 768 KB Output is correct
12 Correct 15 ms 768 KB Output is correct
13 Correct 16 ms 768 KB Output is correct
14 Correct 15 ms 768 KB Output is correct
15 Correct 17 ms 768 KB Output is correct
16 Correct 15 ms 640 KB Output is correct
17 Correct 24 ms 640 KB Output is correct
18 Correct 1131 ms 11916 KB Output is correct
19 Correct 1091 ms 12124 KB Output is correct
20 Correct 1137 ms 12032 KB Output is correct
21 Correct 1103 ms 12256 KB Output is correct
22 Correct 1160 ms 12256 KB Output is correct
23 Correct 1417 ms 11060 KB Output is correct
24 Correct 1418 ms 10932 KB Output is correct
25 Correct 1368 ms 11264 KB Output is correct
26 Correct 39 ms 3832 KB Output is correct
27 Correct 1138 ms 10968 KB Output is correct
28 Correct 1109 ms 10900 KB Output is correct
29 Correct 828 ms 10904 KB Output is correct
30 Correct 984 ms 11092 KB Output is correct
31 Correct 842 ms 9212 KB Output is correct
32 Correct 658 ms 5468 KB Output is correct
33 Correct 996 ms 9228 KB Output is correct
34 Correct 908 ms 9156 KB Output is correct
35 Correct 39 ms 3832 KB Output is correct
36 Correct 940 ms 9020 KB Output is correct
37 Correct 780 ms 9164 KB Output is correct
38 Correct 712 ms 9404 KB Output is correct
39 Correct 576 ms 8928 KB Output is correct
40 Correct 531 ms 8696 KB Output is correct
41 Correct 622 ms 9104 KB Output is correct
42 Correct 570 ms 9336 KB Output is correct
43 Correct 1739 ms 15672 KB Output is correct
44 Correct 53 ms 3960 KB Output is correct
45 Correct 377 ms 9756 KB Output is correct
46 Correct 356 ms 9816 KB Output is correct
47 Correct 1612 ms 14244 KB Output is correct
48 Correct 1700 ms 15656 KB Output is correct
49 Correct 1599 ms 14116 KB Output is correct
50 Correct 880 ms 10692 KB Output is correct
51 Correct 884 ms 10980 KB Output is correct
52 Correct 916 ms 10744 KB Output is correct
53 Correct 1643 ms 13564 KB Output is correct
54 Correct 1592 ms 13820 KB Output is correct
55 Correct 1580 ms 13708 KB Output is correct
56 Correct 1615 ms 14180 KB Output is correct
57 Correct 1626 ms 14404 KB Output is correct
58 Correct 1905 ms 15620 KB Output is correct
59 Correct 1901 ms 15804 KB Output is correct
60 Correct 1853 ms 15556 KB Output is correct
61 Correct 1856 ms 15676 KB Output is correct
62 Correct 1790 ms 14460 KB Output is correct
63 Correct 1744 ms 14352 KB Output is correct
64 Correct 1815 ms 15456 KB Output is correct
65 Correct 1580 ms 12916 KB Output is correct
66 Correct 1099 ms 12020 KB Output is correct
67 Correct 1338 ms 12048 KB Output is correct
68 Correct 1157 ms 12192 KB Output is correct
69 Correct 925 ms 12032 KB Output is correct
70 Correct 1309 ms 11876 KB Output is correct
71 Correct 1289 ms 12292 KB Output is correct
72 Correct 1310 ms 12048 KB Output is correct
73 Correct 1146 ms 12392 KB Output is correct
74 Correct 1161 ms 12052 KB Output is correct
75 Correct 1087 ms 12220 KB Output is correct
76 Correct 972 ms 12044 KB Output is correct
77 Correct 971 ms 12224 KB Output is correct
78 Correct 995 ms 12100 KB Output is correct
79 Correct 840 ms 11504 KB Output is correct
80 Correct 826 ms 11336 KB Output is correct
81 Correct 827 ms 11452 KB Output is correct
82 Correct 820 ms 12208 KB Output is correct
83 Correct 723 ms 12088 KB Output is correct
84 Correct 761 ms 12036 KB Output is correct
85 Correct 1604 ms 16604 KB Output is correct
86 Correct 373 ms 9716 KB Output is correct
87 Correct 351 ms 9888 KB Output is correct
88 Correct 1702 ms 15136 KB Output is correct
89 Correct 1622 ms 16484 KB Output is correct
90 Correct 1515 ms 15096 KB Output is correct
91 Correct 1245 ms 11828 KB Output is correct
92 Correct 1176 ms 12348 KB Output is correct
93 Correct 1429 ms 11176 KB Output is correct
94 Correct 1634 ms 14916 KB Output is correct
95 Correct 1601 ms 14936 KB Output is correct
96 Correct 1801 ms 14244 KB Output is correct
97 Correct 1605 ms 14100 KB Output is correct
98 Correct 1613 ms 14668 KB Output is correct
99 Correct 1844 ms 16344 KB Output is correct
100 Correct 1913 ms 16536 KB Output is correct
101 Correct 1782 ms 16440 KB Output is correct
102 Correct 1957 ms 16660 KB Output is correct
103 Correct 2130 ms 14216 KB Output is correct
104 Correct 2071 ms 14268 KB Output is correct
105 Correct 1613 ms 14356 KB Output is correct
106 Correct 1317 ms 13928 KB Output is correct
107 Correct 1445 ms 14392 KB Output is correct
108 Correct 2338 ms 15480 KB Output is correct
109 Correct 1908 ms 12832 KB Output is correct