Submission #284530

#	Time	Username	Problem	Language	Result	Execution time	Memory
284530		WLZ	Bridges (APIO19_bridges)	C++14	100 / 100	2338 ms	16660 KiB

bridges

#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;
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27