Submission #418736

#	Time	Username	Problem	Language	Result	Execution time	Memory
418736		pauloamed	Bridges (APIO19_bridges)	C++14	0 / 100	3070 ms	26724 KiB

bridges

#include<bits/stdc++.h>
using namespace std;

#define MAXN 500010
#define BLOCK 100

struct DSU{
  int numComponents;
  int sizes[MAXN]; // vetor com tamanhos
  int parents[MAXN]; // vetor com pai de cada no
  stack<pair<int,int>> lastPar, lastSize;
  vector<int> checkpoints;

  DSU(int n){
    checkpoints.push_back(0);
    numComponents = n;
    for(int i = 1; i <= n; ++i){
        sizes[i] = 1; // tamanho inicial
        parents[i] = i; // valor padrao: cada um eh seu pai
    }
  }

  int find(int current){
      int newRoot = current; // variavel para guardar nova raiz
      while(newRoot != parents[newRoot]) // enquanto nao encontro no raiz
          newRoot = parents[newRoot]; // subo na arvore

      // compressao de caminho (*) REMOVER SE FOR ROLLBACK
      int next; // backup do pai
      while(parents[current] != newRoot){ // enquanto nao acho a nova raiz
          next = parents[current]; // faco o backup do pai
          parents[current] = newRoot; // digo que o pai eh a raiz achada (*)
      }

      return newRoot; // retornamo a raiz da arvore
  }

  void onion(int a, int b){
      a = find(a); b = find(b); // unimos uma raiz a outra

      if(a == b) return; // se for a mesma raiz, nao tenho o que unir

      // uniao por tamanho
      if(sizes[a] < sizes[b]) swap(a,b); // quero unir "b" a "a"

      checkpoints.back()++;
      lastSize.push({a, sizes[a]});
      lastPar.push({b, parents[b]});

      sizes[a] += sizes[b]; // atualizando tamanho de "a"
      parents[b] = a; // pai de "b" eh "a"
      numComponents--;
  }

  void check(){
    checkpoints.push_back(0);
  }

  void rollback(){
    int x = checkpoints.back();
    numComponents += x;
    while (x--) {
      sizes[lastSize.top().first] = lastSize.top().second; lastSize.pop();
      parents[lastPar.top().first] = lastPar.top().second; lastPar.pop();
    }
    checkpoints.pop_back();
  }
};

vector<int> cost = {-1};
vector<int> v[MAXN];
vector<pair<int,int>> edges = {{-1, -1}};
vector<pair<int, pair<int,int>>> qs;
/*
first: tipo 1 (update) ou 2 (query)
second:
  tipo 1: first (edge id), second (new weight)
  tipo 2: first (node id), second (cars weight)
*/

vector<pair<int,int>> getSafeEdges(int l, int r, int m){
  set<int> alteredEdges;
  for(int j = l; j <= r; ++j){
    if(qs[j].first == 1){
      int edgeId = qs[j].second.first;
      alteredEdges.insert(edgeId);
    }
  }
  // TODAS ARESTAS ALTERADAS ESTAO EM ALTERED_EDGES

  vector<pair<int,int>> safeEdges;
  for(int j = 1; j <= m; ++j){
    if(alteredEdges.count(j) == 0){
      safeEdges.push_back({cost[j], j});
    }
  }
  // TODAS ARESTAS NAO ALTERADAS ESTAO EM SAFE_EDGES
  // ORDENADAS CRESCENTE PELO CUSTO
  sort(safeEdges.rbegin(), safeEdges.rend());

  return safeEdges;
}


vector<pair<int,int>> getWeightQueries(int l, int r){
  vector<pair<int,int>> weightQueries;
  for(int j = l; j <= r; ++j){
    if(qs[j].first == 2){
      int weight = qs[j].second.second;
      weightQueries.push_back({weight, j});
    }
  }
  sort(weightQueries.rbegin(), weightQueries.rend());
  return weightQueries;
}

int main(){
  iostream::sync_with_stdio(false);
  int n, m; cin >> n >> m;

  for(int i = 0; i < m; ++i){
    int a, b, c; cin >> a >> b >> c;
    v[a].push_back(b);
    v[b].push_back(a);

    cost.push_back(c);
    edges.push_back({a, b});
  }

  int q; cin >> q;
  for(int i = 0; i < q; i++){
    int a, b, c; cin >> a >> b >> c;
    qs.push_back({a, {b, c}});
  }

  vector<int> ans(q, -1);
  for(int i = 0; i < q; i += BLOCK){
    DSU dsu(n);
    int l = i;
    int r = min(q - 1, i + BLOCK);

    //////////////////////////////////////////////////////////////
    // solving range
    auto safeEdges = getSafeEdges(l, r, m);

    // sorting queries
    auto weightQueries = getWeightQueries(l, r);

    int nextSafeEdge = 0;
    for(int j = 0; j < weightQueries.size(); ++j){
      int currWeight = weightQueries[j].first;

      while(nextSafeEdge < safeEdges.size() && safeEdges[nextSafeEdge].first >= currWeight){
        int edgeId = safeEdges[nextSafeEdge].second;
        int a = edges[edgeId].first;
        int b = edges[edgeId].second;
        dsu.onion(a, b);
        nextSafeEdge++;
        // cout << "addei\n";
      }

      dsu.check();

      // adiciona os updt da range
      // quero adicionar todos os updt do bloco ate chegar em mim
      int currIndex = weightQueries[j].second;
      for(int k = l; k <= r; ++k){
        if(qs[k].first == 1){
          int edgeId = qs[k].second.first;
          int a = edges[edgeId].first;
          int b = edges[edgeId].second;

          int w = qs[k].second.second;
          if(k > currIndex) w = cost[edgeId];

          if(w >= currWeight) dsu.onion(a, b);
        }
      }

      int currCity = qs[currIndex].second.first;
      // cout << currCity << " " << currIndex << " " << dsu.sizes[dsu.find(currCity)] <<"\n";
      ans[currIndex] = dsu.sizes[dsu.find(currCity)];

      dsu.rollback();
    }


    //////////////////////////////////////////////////////////////
    // updt weights
    for(int j = l; j <= r; ++j){
      if(qs[j].first == 1){
        int edgeId = qs[j].second.first;
        int newWeight = qs[j].second.second;
        cost[edgeId] = newWeight;
      }
    }
  }

  for(auto x : ans){
    if(x != -1) cout << x << "\n";
  }

}

Compilation message (stderr)

bridges.cpp: In member function 'int DSU::find(int)':
bridges.cpp:29:11: warning: variable 'next' set but not used [-Wunused-but-set-variable]
   29 |       int next; // backup do pai
      |           ^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for(int j = 0; j < weightQueries.size(); ++j){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:153:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |       while(nextSafeEdge < safeEdges.size() && safeEdges[nextSafeEdge].first >= currWeight){
      |             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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