Submission #1175317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175317		JelalTkm	Bridges (APIO19_bridges)	C++17	43 / 100	138 ms	7852 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1000 + 10;
const int md = 1e9 + 7;
const int INF = 5e6;

struct node {
  int u, v, w;
};

vector<multiset<pair<int, int>>> g(N, multiset<pair<int, int>> ());

int bfs(int start, int wj) {
  vector<bool> visited(g.size());
  queue<int> q;
  q.push(start);

  int ans = 0;

  while (!q.empty()) {
    int v = q.front();
    q.pop();
    if (!visited[v]) {
      ans++;
      for (auto i : g[v]) {;
        if (!visited[i.first] && i.second >= wj)
          q.push(i.first);
      }
      visited[v] = 1;
    }
  }

  return ans;
}

struct segtree {
 
  vector<int> tree;
  int size;
 
  void init(int n) {
    size = 1;
    while (size < n) size <<= 1;
    tree.assign(2 * size - 1, 0);
  }
 
  // void build(vector<int> &a, int x, int lx, int rx) {
  //   if (rx - lx == 1) {
  //     if (lx < (int) a.size())
  //       tree[x] = a[lx];
  //   } else {
  //     int m = (lx + rx) >> 1;
  //     build(a, 2 * x + 1, lx, m);
  //     build(a, 2 * x + 2, m, rx);
  //     tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
  //   }
  // }
 
  // void build(vector<int> &a) {
  //   init((int) a.size());
  //   build(a, 0, 0, size);
  // }
 
  void set(int i, int v, int x, int lx, int rx) {
    if (rx - lx == 1) {
      tree[x] = v;
      return;
    }
    int m = (lx + rx) >> 1;
    if (i < m) {
      set(i, v, 2 * x + 1, lx, m);
    } else {
      set(i, v, 2 * x + 2, m, rx);
    }
    tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);
  }
 
  void set(int i, int v) {
    set(i, v, 0, 0, size);
  }
 
  int get(int l, int w, int x, int lx, int rx) {
    if (l >= rx || tree[x] >= w) {
      return INF;
    }
    if (rx - lx == 1) {
      return lx;
    }
    int m = (lx + rx) >> 1;
    int s1 = get(l, w, 2 * x + 1, lx, m);
    if (s1 != INF)
      return s1;
    else return get(l, w, 2 * x + 2, m, rx);
  }
 
  int get(int l, int w) {
    return get(l, w, 0, 0, size);
  }

  int get2(int r, int w, int x, int lx, int rx) {
    if (lx >= r || tree[x] >= w) {
      return 0;
    }
    if (rx - lx == 1) {
      return lx;
    }
    int m = (lx + rx) >> 1;
    int s2 = get2(r, w, 2 * x + 2, m, rx);
    if (s2 != 0)
      return s2;
    else return get2(r, w, 2 * x + 1, lx, m);
  }
 
  int get2(int r, int w) {
    return get2(r, w, 0, 0, size);
  }
};

bool cmp(tuple<int, int, int, int> &t1, tuple<int, int, int, int> &t2) {
  auto [tp, a, b, ind] = t1;
  auto [tp1, a1, b1, ind1] = t2;
  return b > b1;
}

bool cmp1(node &t1, node &t2) {
  return t1.w > t2.w;
}

class DisjointSets {

  private:
  vector<int> p, sz;

  public:
    DisjointSets(int n) : p(n), sz(n) {
      for (int i = 0; i < n; i++) { p[i] = i;sz[i] = 1;}
    }

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

  void unite(int u, int v) {
    u = get(u);
    v = get(v);
    if (u == v) {
      return;
    }
    if (sz[u] < sz[v])
      swap(u, v);
    p[v] = u;
    sz[u] += sz[v];
    sz[v] = 0;
    return;
  }

  int get_sz(int u) {
    u = get(u);
    return sz[u];
  }
  
};

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  // cin >> T;
  while (T--) {
    int n, m;
    cin >> n >> m;
    bool ok = 1;
    vector<node> a(m + 1);
    for (int i = 1; i <= m; i++) {
      cin >> a[i].u >> a[i].v >> a[i].w;
      if (!(a[i].u == i && a[i].v == (i + 1)))
        ok = 0;
    }

    if (ok && m == (n - 1)) {
      segtree st;
      st.init(n + 3);
      for (int i = 1; i <= m; i++)
        st.set(a[i].u, a[i].w);
      st.set(n, 0);
      st.set(0, 0);

      int q;
      cin >> q;
      while (q--) {
        int tp;
        cin >> tp;
        if (tp == 1) {
          int b, r;
          cin >> b >> r;
          st.set(b, r);
        } else {
          int s, w;
          cin >> s >> w;
          int x;
          int y;
            x = st.get(s, w);
            y = st.get2(s, w);
          cout << (x - s) + 1 + (s - y - 1) << '\n';
        }
      }
      continue;
    }

    int q;
    cin >> q;
    vector<tuple<int, int, int, int>> que;
    bool oko = 1;
    for (int i = 0; i < q; i++) {
      int tp, aa, bb;
      cin >> tp >> aa >> bb;
      que.push_back({tp, aa, bb, i});
      if (tp == 1)
        oko = 0;
    }

    if (!oko) {
      for (int i = 1; i <= m; i++) {
        g[a[i].v].insert({a[i].u, a[i].w});
        g[a[i].u].insert({a[i].v, a[i].w});
      }
      for (int i = 0; i < q; i++) {
        auto [tp, b, r, ind] = que[i];
        if (tp == 1) {
          g[a[b].u].erase(g[a[b].u].find({a[b].v, a[b].w}));
          g[a[b].v].erase(g[a[b].v].find({a[b].u, a[b].w}));
          g[a[b].u].insert({a[b].v, r});
          g[a[b].v].insert({a[b].u, r});
          a[b].w = r;
        } else {
          cout << bfs(b, r) << '\n';
        }
      }
    } else {
      DisjointSets dsu(n + 1);
      sort(que.begin(), que.end(), cmp);
      sort(a.begin(), a.end(), cmp1);
      int id = 0;
      vector<int> ans(q);
      for (int i = 0; i < m; i++) {
        do {
          auto [tp, aa, bb, ind] = que[id];
          if (a[i].w < bb) {
            ans[ind] = dsu.get_sz(aa);
            id++;
          } else break;
          if (id == q) break;
        } while (true);
        dsu.unite(a[i].u, a[i].v);
      }

      for (int i = id; i < q; i++) {
        auto [tp, aa, bb, ind] = que[i];
        ans[ind] = dsu.get_sz(aa);
      }

      for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
    }
  }

  return 0;
}

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