Submission #319071

#	Time	Username	Problem	Language	Result	Execution time	Memory
319071		tushar_2658	Bridges (APIO19_bridges)	C++14	100 / 100	2320 ms	36344 KiB

bridges

#include "bits/stdc++.h"
using namespace std;
 
const int maxn = 100005;
 
int type[maxn], idx[maxn], W[maxn];
 
int x[maxn], y[maxn], w[maxn];
 
int n, m;
int magic;
 
int get_block(int idx){
  if(idx == 0)return 0;
  return idx / magic;
}
 
int par[maxn], sz[maxn];
stack<int> st;
int ans[maxn];
int cnt = 0, last = 0;
 
int get(int x){
  while(par[x] != x){
    x = par[x];
  }
  return x;
}
 
void unite(int x, int y){
  x = get(x);
  y = get(y);
  if(x == y)return;
  if(sz[x] < sz[y])swap(x, y);
  st.push(y);
  sz[x] += sz[y];
  par[y] = x;
}
 
void rollback(int x){
  while((int)st.size() > x){
    int k = st.top();
    st.pop();
    sz[par[k]] -= sz[k];
    par[k] = k;
  }
}
 
int main(int argc, char const *argv[])
{
  scanf("%d %d", &n, &m);
  for(int i = 0; i < m; ++i){
    scanf("%d %d %d", &x[i], &y[i], &w[i]);
  }
  int Q;
  scanf("%d", &Q);
  magic = 1000;
  for(int i = 0; i < Q; ++i){
    scanf("%d %d %d", &type[i], &idx[i], &W[i]);
    if(type[i] == 1){
      --idx[i];
    }
  }
  vector<pair<int, int>> v[1001];
  for(int i = 0; i < Q; i += magic){
    for(int j = 1; j <= n; ++j){
      par[j] = j;
      sz[j] = 1;
    }
    int l = i, r = min(Q - 1, i + magic - 1);
    vector<int> unchanged;
    vector<int> upd, ask;
    vector<bool> mark(m + 1);
    for(int j = l; j <= r; ++j){
      if(type[j] == 1){
        mark[idx[j]] = 1;
        upd.push_back(j);
      }else {
        ask.push_back(j);
      }
    }
    for(int j = 0; j < m; ++j){
      if(mark[j]){}
      else {
        unchanged.push_back(j);
      }
    }
    for(int j = l; j <= r; ++j){
      if(type[j] == 1){
        w[idx[j]] = W[j];
      }else {
        v[j - l].clear();
        for(auto k : upd){
          if(w[idx[k]] >= W[j]){
            v[j - l].push_back({x[idx[k]], y[idx[k]]});
          }
        }
      }
    }
    sort(unchanged.begin(), unchanged.end(), [&](int x, int y){
      return w[x] > w[y];
    });
    sort(ask.begin(), ask.end(), [&](int x, int y){
      return W[x] > W[y];
    });
    int ptr = 0;
    cnt = last = 0;
    for(auto j : ask){
      while(ptr < (int)unchanged.size()){
        if(w[unchanged[ptr]] >= W[j]){}
        else {
          break;
        }
        unite(x[unchanged[ptr]], y[unchanged[ptr]]);
        ++ptr;
      }
      last = st.size();
      for(auto k : v[j - l]){
        unite(k.first, k.second);
      }
      ans[j] = sz[get(idx[j])];
      rollback(last);
    }
  }
  
  for(int i = 0; i < Q; ++i){
    if(type[i] == 2){
      printf("%d\n", ans[i]);
    }
  }
 
  return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main(int, const char**)':
bridges.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |     scanf("%d %d %d", &x[i], &y[i], &w[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |   scanf("%d", &Q);
      |   ~~~~~^~~~~~~~~~
bridges.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |     scanf("%d %d %d", &type[i], &idx[i], &W[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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