제출 #1174671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174671		JelalTkm	Bridges (APIO19_bridges)	C++17	0 / 100	3093 ms	1096 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 = 1e5;

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 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);
    segtree st;
    st.init(n + 3);
    for (int i = 1; i <= m; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      st.set(u, w);
      // 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 - 1s)) {
      // for (int i = 1; i <= m; i++)
      //   st.set(a[i].u, a[i].w);

      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: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27