Submission #1174668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174668		JelalTkm	Bridges (APIO19_bridges)	C++17	13 / 100	3093 ms	2944 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx")
#pragma GCC target("sse4.2")
#pragma GCC target("popcnt,lzcnt")
#pragma GCC target("fma")

using namespace std;

#define int long long int

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

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, INF);
  }
 
  // 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 r, int w, int x, int lx, int rx) {
    if (l >= rx || lx >= r || tree[x] > w) {
      return INF;
    }
    if (rx - lx == 1) {
      if (tree[x] < w)
        return lx;
      else return INF;
    }
    int m = (lx + rx) >> 1;
    int s1 = get(l, r, w, 2 * x + 1, lx, m);
    if (s1 != INF)
      return s1;
    else return get(l, r, w, 2 * x + 2, m, rx);
  }
 
  int get(int l, int r, int w) {
    return get(l, r, w, 0, 0, size);
  }

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

  int gt() {
    return tree[0];
  }
};

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;
          if (st.gt() > w) {
            x = n, y = 0;
          } else {
            x = st.get(s, n + 1, w);
            y = st.get2(0, s, w);
          }
          cout << (x - s) + 1 + (s - y - 1) << '\n';
        }
      }
      continue;
    }

    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});
    }
    int q;
    cin >> q;
    while (q--) {
      int tp;
      cin >> tp;
      if (tp == 1) {
        int b, r;
        cin >> b >> r;
        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 {
        int s, w;
        cin >> s >> w;
        cout << bfs(s, w) << '\n';
      }
    }
  }

  return 0;
}

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