Submission #187346

#	Time	Username	Problem	Language	Result	Execution time	Memory
187346		MiricaMatei	Bridges (APIO19_bridges)	C++14	100 / 100	2904 ms	10216 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50005;
const int MAXM = 100005;
const int MAXQ = 100005;
const int INF = 1000000000;

struct Edge {
  int u, v, c;
  bool operator < (const Edge& other) const {
    return c > other.c;
  }
}e[MAXM], sg[MAXM];

struct Query {
  int t, a, b, ind;
  bool operator < (const Query& other) const {
    return b > other.b;
  }
} qr[MAXQ], bk[MAXQ];

struct DSU {
  int n;
  int t[MAXN], h[MAXN], sz[MAXN];
  int top = 0;
  int stkx[MAXN], stky[MAXN];

  void init(int _n) {
    n = _n;
    for (int i = 1; i <= n; ++i)
      t[i] = i, h[i] = 1, sz[i] = 1;
    top = 0;
  }

  int f(int x) {
    if (t[x] == x)
      return x;
    return f(t[x]);
  }

  int u(int x, int y) {
    x = f(x);
    y = f(y);
    if (x == y)
      return 0;
    if (h[y] > h[x])
      swap(x, y);
    t[y] = x;
    sz[x] += sz[y];
    if (h[x] == h[y])
      h[x]++;
    top++;
    stkx[top] = x;
    stky[top] = y;
    return 1;
  }

  void undo() {
    int x = stkx[top];
    int y = stky[top];
    top--;
    if (h[x] == h[y] + 1)
      h[x]--;
    t[y] = y;
    sz[x] -= sz[y];
  }

  int query(int x) {
    return sz[f(x)];
  }
}dsu;

bool vis[MAXM];
bool vis1[MAXM];
int ans[MAXM];

int main() {

  int n, m, q;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i)
    scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    scanf("%d%d%d", &qr[i].t, &qr[i].a, &qr[i].b);
    qr[i].ind = i;
  }
  int BUCK_SIZE = 700;
  for (int b = 1; (b - 1) * BUCK_SIZE + 1 <= q; ++b) {
    dsu.init(n);
    for (int i = 1; i <= m; ++i)
      vis[i] = 0;
    int l = (b - 1) * BUCK_SIZE + 1;
    int r = min(q, l + BUCK_SIZE - 1);
    int s = 0;
    for (int i = l; i <= r; ++i) {
      if (qr[i].t == 1)
        vis[qr[i].a] = 1;
      bk[++s] = qr[i];
    }
    int k = 0;
    for (int i = 1; i <= m; ++i)
      if (!vis[i])
        sg[++k] = e[i];
    sort(sg + 1, sg + k + 1);
    sort(bk + 1, bk + s + 1);
    for (int i = 1, j = 1; j <= s;) {
      while (j <= s && bk[j].t == 1)
        j++;
      if (j > s)
        continue;
      if (i <= k && (j > s || sg[i].c >= bk[j].b)) {
        dsu.u(sg[i].u, sg[i].v);
        i++;
      } else {
        int undoCount = 0;
        for (int p = bk[j].ind - 1; p >= l; --p)
          if (qr[p].t == 1 && !vis1[qr[p].a]) {
            vis1[qr[p].a] = 1;
            if (qr[p].b >= bk[j].b)
              undoCount += dsu.u(e[qr[p].a].u, e[qr[p].a].v);
          }
        for (int p = bk[j].ind + 1; p <= r; ++p)
          if (qr[p].t == 1 && !vis1[qr[p].a]) {
            vis1[qr[p].a] = 1;
            if (e[qr[p].a].c >= bk[j].b)
              undoCount += dsu.u(e[qr[p].a].u, e[qr[p].a].v);
          }
        ans[bk[j].ind] = dsu.query(bk[j].a);
        for (int p = l; p <= r; ++p)
          if (qr[p].t == 1)
            vis1[qr[p].a] = 0;
        while (undoCount--)
          dsu.undo();
        j++;
      }
    }
    for (int i = l; i <= r; ++i)
      if (qr[i].t == 1)
        e[qr[i].a].c = qr[i].b;
  }

  for (int i = 1; i <= q; ++i)
    if (ans[i])
      printf("%d\n", ans[i]);

  return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
   ~~~~~^~~~~~~~~~
bridges.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &qr[i].t, &qr[i].a, &qr[i].b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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