Submission #419147

#	Time	Username	Problem	Language	Result	Execution time	Memory
419147		pauloamed	Bridges (APIO19_bridges)	C++14	27 / 100	3055 ms	5792 KiB

bridges

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

#define MAXN 100010
#define BLOCK 600
int sizes[MAXN]; // vetor com tamanhos
int parents[MAXN]; // vetor com pai de cada no

struct DSU{
  int numComponents;
  stack<pair<int,int>> lastPar, lastSize;
  vector<int> checkpoints;

  DSU(int n){
    lastPar = lastSize = stack<pair<int,int>>();
    checkpoints = {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
      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<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)
*/

int main(){
  iostream::sync_with_stdio(false);
  cin.tie(NULL);

  int n, m; cin >> n >> m;

  for(int i = 0; i < m; ++i){
    int a, b, c; cin >> a >> b >> c;
    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 l = 0; l < q; l += BLOCK){
    DSU dsu(n);
    int r = min(q - 1, l + BLOCK - 1);

    //////////////////////////////////////////////////////////////

    // TODAS ARESTAS ALTERADAS ESTAO EM ALTERED_EDGES

    vector<pair<int,int>> safeEdges;
    vector<pair<int,int>> weightQueries;
    vector<int> unsafeEdges;

    // solving range
    vector<bool> alteredEdges(m + 1);
    for(int i = l; i <= r; ++i){
      if(qs[i].first == 1){
        int edgeId = qs[i].second.first;
        alteredEdges[edgeId] = true;
        unsafeEdges.push_back(i);
      }else{
        int weight = qs[i].second.second;
        weightQueries.push_back({weight, i});
      }
    }

    for(int i = 1; i <= m; ++i){
      if(alteredEdges[i] == 0){
        safeEdges.push_back({cost[i], i});
      }
    }
    // TODAS ARESTAS NAO ALTERADAS ESTAO EM SAFE_EDGES
    // ORDENADAS DECRESCENTE PELO CUSTO


    sort(weightQueries.rbegin(), weightQueries.rend());
    sort(safeEdges.rbegin(), safeEdges.rend());

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

      // o carro saindo da cidade atual tem peso menor que ou igual ao peso da proxima
      // edge ainda nao adicionada?
      while(nextSafeEdge < safeEdges.size() && currWeight <= safeEdges[nextSafeEdge].first){
        int edgeId = safeEdges[nextSafeEdge].second;
        dsu.onion(edges[edgeId].first, edges[edgeId].second);
        nextSafeEdge++;
      }

      dsu.check();

      // adiciona os updt da range
      // quero adicionar todos os updt do bloco ate chegar em mim
      // e os q passam de mim so q com o peso original
      int currIndex = weightQueries[i].second;
      int currCity = qs[currIndex].second.first;


      map<int, int> ws;
      int j = 0;
      for(; j < unsafeEdges.size(); j++){
        int k = unsafeEdges[j];
        if(k > currIndex) break;
        int edgeId = qs[k].second.first;
        int newWeight = qs[k].second.second;
        ws[edgeId] = newWeight;
      }

      for(;j < unsafeEdges.size(); ++j){
        int k = unsafeEdges[j];
        int edgeId = qs[k].second.first;
        if(ws.count(edgeId) == 0) ws[edgeId] = cost[edgeId];
      }

      for(auto x : ws){
        if(currWeight <= x.second){
          dsu.onion(edges[x.first].first, edges[x.first].second);
        }
      }

      ans[currIndex] = sizes[dsu.find(currCity)];
      dsu.rollback();
    }

    for(int j = 0; j < unsafeEdges.size(); j++){
      int k = unsafeEdges[j];
      int edgeId = qs[k].second.first;
      int newWeight = qs[k].second.second;
      cost[edgeId] = newWeight;
    }
  }

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

}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:130: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]
  130 |     for(int i = 0; i < weightQueries.size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:135: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]
  135 |       while(nextSafeEdge < safeEdges.size() && currWeight <= safeEdges[nextSafeEdge].first){
      |             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:152:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |       for(; j < unsafeEdges.size(); j++){
      |             ~~^~~~~~~~~~~~~~~~~~~~
bridges.cpp:160:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |       for(;j < unsafeEdges.size(); ++j){
      |            ~~^~~~~~~~~~~~~~~~~~~~
bridges.cpp:176:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |     for(int j = 0; j < unsafeEdges.size(); j++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~

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