제출 #319068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
319068		tushar_2658	Bridges (APIO19_bridges)	C++14	0 / 100	3037 ms	70820 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];
bool mark[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 = sqrt(Q) + 1;
  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[maxn];
  for(int i = 0; i < Q; i += magic){
    iota(par, par + n + 1, 0);
    fill(sz + 1, sz + n + 1, 1);
    fill(mark + 1, mark + m, false);
    int l = i, r = min(Q - 1, i + magic - 1);
    vector<int> upd, ask, unchanged;
    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]){
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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