Submission #419110

#	Time	Username	Problem	Language	Result	Execution time	Memory
419110		pauloamed	Bridges (APIO19_bridges)	C++14	14 / 100	1791 ms	9504 KiB

bridges

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

#define MAXN 100010
#define BLOCK 1000
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)
*/

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

  vector<pair<int,int>> safeEdges;
  for(int i = 1; i <= m; ++i){
    if(alteredEdges.count(i) == 0){
      safeEdges.push_back({cost[i], i});
    }
  }
  // TODAS ARESTAS NAO ALTERADAS ESTAO EM SAFE_EDGES
  // ORDENADAS DECRESCENTE 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 i = l; i <= r; ++i){
    if(qs[i].first == 2){
      int weight = qs[i].second.second;
      weightQueries.push_back({weight, i});
    }
  }
  sort(weightQueries.rbegin(), weightQueries.rend());
  return weightQueries;
}


void updt(int l, int r){
  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;
    }
  }
}


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);

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

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

    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;
      for(int k = l; k <= r; ++k){
        if(qs[k].first == 1){
          int edgeId = qs[k].second.first;
          int newWeight = qs[k].second.second;
          int w = ((k > currIndex)? cost[edgeId] : newWeight);

          if(currWeight <= w){
            dsu.onion(edges[edgeId].first, edges[edgeId].second);
          }
        }
      }

      int currCity = qs[currIndex].second.first;
      ans[currIndex] = sizes[dsu.find(currCity)];

      dsu.rollback();
    }

    updt(l, r);
  }

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

}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:152: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]
  152 |     for(int i = 0; i < weightQueries.size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:157: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]
  157 |       while(nextSafeEdge < safeEdges.size() && currWeight <= safeEdges[nextSafeEdge].first){
      |             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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