제출 #319057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
319057		tushar_2658	다리 (APIO19_bridges)	C++14	59 / 100	3085 ms	70152 KiB

bridges

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

const int maxn = 100005;

struct DATA {
  int type, idx, w, id;
  DATA(int _type, int _idx, int _w, int _id){
    type = _type, idx = _idx, w = _w, id = _id;
  }
  DATA(){}
};

int x[maxn], y[maxn], w[maxn];

int n, m;
int magic;
DATA q[maxn];

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);
  for(int i = 0; i < Q; ++i){
    scanf("%d %d %d", &q[i].type, &q[i].idx, &q[i].w);
    q[i].id = i;
    if(q[i].type == 1){
      --q[i].idx;
    }
  }
  vector<pair<int, int>> v[405];
  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(q[j].type == 1){
        mark[q[j].idx] = 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(q[j].type == 1){
        w[q[j].idx] = q[j].w;
      }else {
        v[j - l].clear();
        for(auto k : upd){
          if(w[q[k].idx] >= q[j].w){
            v[j - l].push_back({x[q[k].idx], y[q[k].idx]});
          }
        }
      }
    }
    sort(unchanged.begin(), unchanged.end(), [&](int x, int y){
      return w[x] > w[y];
    });
    sort(ask.begin(), ask.end(), [&](int x, int y){
      return q[x].w > q[y].w;
    });
    int ptr = 0;
    cnt = last = 0;
    for(auto j : ask){
      while(ptr < (int)unchanged.size()){
        if(w[unchanged[ptr]] >= q[j].w){}
        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[q[j].id] = sz[get(q[j].idx)];
      rollback(last);
    }
  }
  
  for(int i = 0; i < Q; ++i){
    if(q[i].type == 2){
      printf("%d\n", ans[i]);
    }
  }

  return 0;
}

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

bridges.cpp: In function 'int main(int, const char**)':
bridges.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
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", &x[i], &y[i], &w[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |   scanf("%d", &Q);
      |   ~~~~~^~~~~~~~~~
bridges.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d %d %d", &q[i].type, &q[i].idx, &q[i].w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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