Submission #716883

#	Time	Username	Problem	Language	Result	Execution time	Memory
716883		YENGOYAN	Bridges (APIO19_bridges)	C++17	100 / 100	2489 ms	36240 KiB

bridges

/*
                                    //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
                                    \\                                    //
                                    //  271828___182845__904523__53602__  \\
                                    \\  87___47____13______52____66__24_  //
                                    //  97___75____72______47____09___36  \\
                                    \\  999595_____74______96____69___67  //
                                    //  62___77____24______07____66__30_  \\
                                    \\  35___35____47______59____45713__  //
                                    //                                    \\
                                    \\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>
#include <functional>

using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e18;

vector<int> dx = { 1, 0, -1, 0, 1, -1, 1, -1 };
vector<int> dy = { 0, -1, 0, 1, -1, 1, 1, -1 };

void solve() {
  int n, m; cin >> n >> m;
  vector<int> u(m + 1), v(m + 1), w(m + 1);
  for(int i = 1; i <= m; ++i){
    cin >> u[i] >> v[i] >> w[i];
  }
  int q; cin >> q;
  vector<int> t(q+1), x(q+1), y(q+1);
  for(int i = 1; i <= q; ++i){
    cin >> t[i] >> x[i] >> y[i];
  }
  vector<int> par(n + 1), sz(n + 1);
  stack<int> st;
  for(int i = 1; i <= n; ++i){
    sz[i] = 1;
    par[i] = i;
  }
  function<int(int)> get = [&](int u){
    while(par[u] != u){
      u = par[u];
    }
    return u;
  };
  function<void(int, int)> union_sets = [&](int u, int v){
    int a = get(u), b = get(v);
    if(a == b) {
      return;
    }
    if(sz[a] < sz[b]){
      swap(a, b);
    }
    st.push(b);
    sz[a] += sz[b];
    par[b] = a;
  };
  function<void(int)> rollback = [&](int x){
    while(st.size() > x){
      int node = st.top();
      st.pop();
      sz[par[node]] -= sz[node];
      par[node] = node;
//      st.pop();
    }
  };
  vector<vector<int>> to_join(805);
  int block_size = 800;
  vector<int> ans(q + 1);
  for(int i = 1; i <= q; i += block_size){
    for(int i = 1; i <= n; ++i){
      par[i] = i;
      sz[i] = 1;
    }
    int l = i, r = min(q, i + block_size - 1);
    vector<int> qry, upd, unch;
    vector<bool> vis(m + 1);
    for(int j = l; j <= r; ++j){
      if(t[j] == 1){
        upd.push_back(j);
        vis[x[j]] = 1;
      }
      else{
        qry.push_back(j);
      }
    }
    for(int j = 1; j <= m; ++j){
      if(!vis[j]){
        unch.push_back(j);
      }
    }
    for(int j = l; j <= r; ++j){
      if(t[j] == 1){
        w[x[j]] = y[j];
      }
      else{
        to_join[j - l].clear();
        for(int &k : upd){
          if(w[x[k]] >= y[j]){
            to_join[j - l].push_back(x[k]);
          }
        }
      }
    }
    sort(qry.begin(), qry.end(), [&](int a, int b) {return y[a] > y[b];});
    sort(unch.begin(), unch.end(), [&](int a, int b) {return w[a] > w[b]; });
    int idx = 0;
    for(int &j : qry){
      while(idx < unch.size() && w[unch[idx]] >= y[j]){
        union_sets(u[unch[idx]], v[unch[idx]]);
        ++idx;
      }
      int siz = st.size();
      for(int &k : to_join[j - l]){
        union_sets(u[k], v[k]);
      }
//      cout << j << "\n";
      ans[j] = sz[get(x[j])];
      rollback(siz);
    }
  }

  for(int i = 1; i <= q; ++i){
    if(t[i] == 2){
      cout << ans[i] << "\n";
    }
  }

}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  //int t; cin >> t; while (t--)
    solve();

}

Compilation message (stderr)

bridges.cpp: In lambda function:
bridges.cpp:80:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |     while(st.size() > x){
      |           ~~~~~~~~~~^~~
bridges.cpp: In function 'void solve()':
bridges.cpp:130:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |       while(idx < unch.size() && w[unch[idx]] >= y[j]){
      |             ~~~~^~~~~~~~~~~~~

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