Submission #319051

#	Time	Username	Problem	Language	Result	Execution time	Memory
319051		tushar_2658	Bridges (APIO19_bridges)	C++14	13 / 100	3068 ms	28300 KiB

bridges

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

const int maxn = 200005;

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];
pair<int, int> p[maxn];
int ans[maxn];
int cnt = 0, last = 0;

int get(int x){
  if(par[x] == x)return x;
  else {
    return get(par[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);
  p[++cnt] = {x, y};
  sz[x] += sz[y];
  par[y] = x;
}

void rollback(int x){
  sz[p[x].first] -= sz[p[x].second];
  par[p[x].second] = p[x].second;
}

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[500];
  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<edges> changed, unchanged;
    vector<int> upd, ask;
    vector<int> 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]){
        changed.push_back(E[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;
    for(auto j : ask){
      while(ptr < (int)unchanged.size() && unchanged[ptr].w >= q[j].w){
        unite(unchanged[ptr].u, unchanged[ptr].v);
        last = cnt;
        ++ptr;
      }
      for(auto k : v[j - l]){
        unite(k.first, k.second);
      }
      ans[q[j].id] = sz[get(q[j].idx)];
      while(cnt > last){
        rollback(cnt);
        --cnt;
      }
    }
  }
  
  for(int i = 0; i < Q; ++i){
    if(ans[i]){
      printf("%d\n", ans[i]);
    }
  }

  return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main(int, const char**)':
bridges.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |     scanf("%d %d %d", &E[i].u, &E[i].v, &E[i].w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   scanf("%d", &Q);
      |   ~~~~~^~~~~~~~~~
bridges.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |     scanf("%d %d %d", &q[i].type, &q[i].idx, &q[i].w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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