제출 #319056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
319056		tushar_2658	다리 (APIO19_bridges)	C++14	59 / 100	3081 ms	73908 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(){}
};

struct edges {
  int u, v, w, id;
  edges (int _u, int _v, int _w){
    u = _u, v = _v, w = _w;
  }
  edges(){}
};

int n, m;
int magic;
edges E[maxn];
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", &E[i].u, &E[i].v, &E[i].w);
    E[i].id = 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){
    iota(par + 1, par + n + 1, 1);
    fill(sz + 1, sz + n + 1, 1);
    int l = i, r = min(Q - 1, i + magic - 1);
    vector<edges> 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(E[j]);
      }
    }
    for(int j = l; j <= r; ++j){
      if(q[j].type == 1){
        E[q[j].idx].w = q[j].w;
      }else {
        v[j - l].clear();
        for(auto k : upd){
          if(E[q[k].idx].w >= q[j].w){
            v[j - l].push_back({E[q[k].idx].u, E[q[k].idx].v});
          }
        }
      }
    }
    sort(unchanged.begin(), unchanged.end(), [&](edges x, edges y){
      return x.w > y.w;
    });
    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(unchanged[ptr].w >= q[j].w){}
        else {
          break;
        }
        unite(unchanged[ptr].u, unchanged[ptr].v);
        ++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:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%d %d %d", &E[i].u, &E[i].v, &E[i].w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |   scanf("%d", &Q);
      |   ~~~~~^~~~~~~~~~
bridges.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     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