Submission #419155

#	Time	Username	Problem	Language	Result	Execution time	Memory
419155		pauloamed	Bridges (APIO19_bridges)	C++14	100 / 100	2996 ms	11380 KiB

bridges

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

#define MAXN 100010
#define BLOCK 900
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> unsafeQueries, unsafeEdges;

    // solving range
    vector<int> alteredEdges(m + 1);
    for(int i = l; i <= r; ++i){
      if(qs[i].first == 1){
        int edgeId = qs[i].second.first;
        alteredEdges[edgeId] = 1;
        unsafeQueries.push_back(i);
        unsafeEdges.push_back(edgeId);
      }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());

    sort(unsafeEdges.begin(), unsafeEdges.end());
    unsafeEdges.resize(unique(unsafeEdges.begin(), unsafeEdges.end()) - unsafeEdges.begin());

    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;


      for(auto x : unsafeEdges) alteredEdges[x] = 0;
      for(int j = 0; j < unsafeQueries.size(); j++){
        int k = unsafeQueries[j];
        int edgeId = qs[k].second.first;
        if(k > currIndex){
          if(alteredEdges[edgeId] == 0) alteredEdges[edgeId] = cost[edgeId];
        }else{
          int newWeight = qs[k].second.second;
          alteredEdges[edgeId] = newWeight;
        }
      }

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

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

    for(int j = 0; j < unsafeQueries.size(); j++){
      int k = unsafeQueries[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:134: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]
  134 |     for(int i = 0; i < weightQueries.size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:139: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]
  139 |       while(nextSafeEdge < safeEdges.size() && currWeight <= safeEdges[nextSafeEdge].first){
      |             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:155:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |       for(int j = 0; j < unsafeQueries.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 < unsafeQueries.size(); 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