Bình luận

• 
  

  0

  

  haiduong151109  đã bình luận lúc 18, Tháng 9, 2025, 5:03

  https://ideone.com/ILXusL sao code e sai 1 nửa test v ạ

• 
  

  0

  

  pppssslc  đã bình luận lúc 18, Tháng 9, 2025, 12:59

  Đề bài có nêu là:

  • Trong cùng một thời điểm có thể có nhiều cạnh nối giữa hai đỉnh ~x~ và ~y~(Đa đồ thị).
  • Đối với truy vấn loại ~2~, nếu có nhiều cạnh ~(x, y)~ thì xóa cạnh bất kì; nếu không có cạnh nào, không làm gì cả.

  Đây là đa đồ thị, bạn chưa xử lí trường hợp có nhiều cạnh ~(x, y)~ cùng tồn tại cùng một thời điểm.

• 
  

  0

  

  haiduong151109  đã bình luận lúc 18, Tháng 9, 2025, 15:07

  really thanks bro nhiều

• 
  

  3

  

  pppssslc  đã bình luận lúc 24, Tháng 8, 2025, 13:02 ← chỉnh sửa →

  Unoffical solution:

  segment tree + dsu rollback

  • Vì cạnh được thêm và xóa theo thời gian, ta cần một cấu trúc theo dõi sự tồn tại của cạnh theo khoảng thời gian.
  • Ta dùng Segment Tree để lưu các khoảng thời gian mà một cạnh tồn tại.
  • Sau đó ta sẽ duyệt cái Segment Tree đó. Dùng DSU với rollback (undo) để quản lý các thành phần liên thông khi duyệt Segment Tree.

  Code mẫu:

  // Date: 24/08/2025
  // Author: pppssslc
  #include<bits/stdc++.h>
  
  using namespace std;
  
  template<class X, class Y> void mini(X &x, const Y &y){
      x = min(x, y);
  }
  
  template<class X, class Y> void maxi(X &x, const Y &y){
      x = max(x, y);
  }
  
  typedef string str;
  typedef long long ll;
  typedef unsigned long long ull;
  typedef __int128 i128;
  typedef double db;
  typedef long double ldb;
  typedef pair<int, int> pii;
  typedef pair<ll, ll> pll;
  typedef vector<int> vi;
  typedef vector<ll> vl;
  typedef vector<char> vc;
  typedef vector<pii> vpii;
  typedef vector<pll> vpll;
  typedef vector<vector<int>> vii;
  typedef vector<vector<ll>> vll;
  typedef vector<vector<char>> vcc;
  typedef map<int, int> mpii;
  typedef map<ll, ll> mpll;
  typedef set<int> si;
  typedef set<ll> sl;
  typedef complex<double> cd;
  
  #define se second
  #define fi first
  #define Rep(i, l, r, x) for(int i = l; i < (int)r; i += x)
  #define Repd(i, l, r, x) for(int i = l; i > (int)r; i -= x)
  #define For(i, l, r, x) for(int i = l; i <= (int)r; i += x)
  #define Ford(i, l, r, x) for(int i = l; i >= (int)r; i -= x)
  #define Fore(x, a) for(auto x: a)
  #define pb push_back
  #define pf push_front
  #define pp pop_back
  #define ppf pop_front
  #define ins insert
  #define era erase
  #define upb upper_bound
  #define lwb lower_bound
  #define all(a) a.begin(), a.end()
  
  struct qry{
      int t, u, v;
  };
  
  struct dsu{
      vi par;
      vi sz;
      stack<pair<pii, pii>> his;
  
      dsu(int n){
          par.resize(n + 1);
          sz.resize(n + 1);
          For(i, 1, n, 1)
              par[i] = i, sz[i] = 1;
      }
  
      int find(int i){
          while(par[i] != i) i = par[i];
          return i;
      }
  
      void uni(int u, int v){
          int ru = find(u), rv = find(v);
          if(ru != rv){
              if(sz[ru] < sz[rv]) swap(ru, rv);
              his.push({{rv, par[rv]}, {ru, sz[ru]}});
              par[rv] = ru, sz[ru] += sz[rv];
          }else his.push({{-1, -1}, {-1, -1}});
      }
  
      void roll(){
          auto last = his.top();
          his.pop();
          if(last.fi.fi == -1) return;
          par[last.fi.fi] = last.fi.se;
          sz[last.se.fi] = last.se.se;
      }
  };
  
  const db PI = acos(-1);
  const ll inf = 1e18 + 1;
  const int mod = 1e9 + 7;
  const int maxn = 1e5 + 1;
  
  int n, q;
  vpii st[maxn * 4];
  vi ans;
  
  void upd(int id, int l, int r, int u, int v, pii e){
      if(r < u || v < l) return;
      if(u <= l && r <= v){
          st[id].pb(e);
          return;
      }
      int m = (l + r) / 2;
      upd(id * 2, l, m, u, v, e);
      upd(id * 2 + 1, m + 1, r, u, v, e);
  }
  
  void get(int id, int l, int r, dsu &dsu, const vector<qry> &qries){
      Fore(e, st[id]) dsu.uni(e.fi, e.se);
      if(l == r){ if(qries[l - 1].t == 3)
          ans.pb(dsu.find(qries[l - 1].u) == dsu.find(qries[l - 1].v));
      }else{
          int m = l + (r - l) / 2;
          get(2 * id, l, m, dsu, qries);
          get(2 * id + 1, m + 1, r, dsu, qries);
      }
      Rep(i, 0, st[id].size(), 1) dsu.roll();
  }
  
  signed main(){
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr); cout.tie(nullptr);
  
      cin >> n >> q;
      vector<qry> qries(q);
      map<pii, stack<int>> edges;
  
      Rep(i, 0, q, 1){
          cin >> qries[i].t >> qries[i].u >> qries[i].v;
          if(qries[i].u > qries[i].v) swap(qries[i].u, qries[i].v);
          if(qries[i].t == 1) edges[{qries[i].u, qries[i].v}].push(i + 1);
          else if(qries[i].t == 2){
              pii key = {qries[i].u, qries[i].v};
              if(edges.count(key) && !edges[key].empty()){
                  int st = edges[key].top();
                  edges[key].pop();
                  upd(1, 1, q, st, i, key);
              }
          }
      }
  
      for(auto &[e, t]: edges){
          while(!t.empty()){
              int st = t.top(); t.pop();
              upd(1, 1, q, st, q, e);
          }
      }
  
      dsu dsu(n);
      get(1, 1, q, dsu, qries);
      Fore(x, ans) cout << x;
      return 0;
  }
  

  ĐPT: ~O(q \cdot log_2 q)~