Submission #493871

#	Time	Username	Problem	Language	Result	Execution time	Memory
493871		cadmiumsky	Bridges (APIO19_bridges)	C++14	29 / 100	3097 ms	9732 KiB

bridges

#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;
const int mmax = 100005;
const int nmax = 50005;
const int qmax = 100005;
int n, m;
#define x first
#define y second

namespace DSU {
  stack< pair<int,int> >undostack;
  int dsu[nmax];
  int area[nmax];
  void init() {
    for(int i = 0; i < n; i++) {
      dsu[i]=i;
      area[i]=1;
    }
    while(!undostack.empty())
      undostack.pop();
  }
  int father(int x) {
    return (dsu[x]==x ? x : father(dsu[x]));
  }
  void unite(int x , int y) {
    x = father(x);
    y = father(y);
    if(x == y)
      return;
    if(area[x] > area[y]) {
      swap(x, y);
    }
    dsu[y] = x;
    area[x] += area[y];
    undostack.push({x, y});
  }
  int gettime() {
    return undostack.size();
  }
  void popundo() {
    int x, y;
    tie(x,y) = undostack.top();
    undostack.pop();
    dsu[y] = y;
    area[x] -= area[y];
    return;
  }
  void rollback(int x) {
    while(undostack.size() > x)
      popundo();
  }
  int query(int x) {
    return area[father(x)];
  }
};

int weight[mmax];
int prevweight[mmax];
pair<int, int> edge[mmax];

int rez[qmax];

struct query {
  int type, x, w, ind;
  bool operator < (const query& camsus) const {
    return w<camsus.w || (w==camsus.w && type%2>camsus.type%2);
  }
}initq[qmax];

static void solve(int l, int r) {
  DSU::init();
  unordered_set< int > used;
  vector< query > inupd;
  vector< query > qs;
  for(int i = l; i <= r; i++) {
    if(initq[i].type == 1) {
      used.insert(initq[i].x);
      inupd.push_back(initq[i]);
    }
    else {
      qs.push_back(initq[i]);
    } 
  }
  for(int i = 0; i < m; i++) {
    if(used.count(i)==0) {
      qs.push_back(query{3, i, weight[i], 0});
    }
  }
  sort(qs.begin(), qs.end());
  for(auto x:qs) {
    if(x.type == 3) {
      DSU::unite(edge[x.x].x, edge[x.x].y);
      //cout << '+' << edge[x.x].x+1 <<' '<< edge[x.x].y+1 <<' '<< weight[x.x]<< '\n';
    }
    else {
      //cout <<'?'<< x.x+1 << ' '<< x.w <<'\n';
      for(auto upd : inupd) {
        if(upd.ind > x.ind)
          break;
        //cout << "!" << upd.ind <<' '<<upd.type <<' '<<upd.x <<' '<<upd.w <<'\n';
        prevweight[upd.x] = upd.w;
      }
      int inittime=DSU::gettime();
      for(auto e : used) {
        if(prevweight[e]<=x.w) {
          //cout << "+-" << 1+edge[e].x <<' '<< 1+edge[e].y << '\n';
          DSU::unite(edge[e].x, edge[e].y);
        }
        prevweight[e]=weight[e];
      }
      rez[x.ind] = DSU::query(x.x);
      DSU::rollback(inittime);
    }
  }
  //cout << '\n';
}
static void fix(int l, int r) {
  for(int i = l; i <= r; i++) {
    if(initq[i].type==1)
      prevweight[initq[i].x] = weight[initq[i].x] = initq[i].w;
  }
  return;
}

int main() {
  int q;
  cin >> n >> m;
  DSU::init();
  for(int i = 0; i < m; i++) {
    cin >> edge[i].x >> edge[i].y >> weight[i];
    --edge[i].x;
    --edge[i].y;
    weight[i] *= -1; // ca imi convine mai mult cu < decat cu > 
    prevweight[i] = weight[i];
    if(edge[i].x > edge[i].y ) {
      swap(edge[i].x, edge[i].y);
    }
  }
  cin >> q;
  for(int i = 0; i < q; i++) {
    cin >> initq[i].type >> initq[i].x >> initq[i].w;
    initq[i].x--;
    initq[i].w *= -1;
    initq[i].ind=i;
  }
  int buck=sqrt(q); // se poate si mai bine
  int l=0,r=buck-1;
  while(l < q) {
    solve(l,r);
    fix(l,r);
    l += buck;
    r=min(q - 1, r + buck);
  }
  for (int i = 0; i < q; i++) {
    if(initq[i].type == 2)
      cout << rez[i] << '\n';
  }
}
/*
5 5
5 3 6
2 4 49
4 1 44
4 3 74
1 2 85
10
2 2 22
2 2 20
1 3 49
====
2 1 77
1 3 44
1 1 6
====
2 3 49
2 4 31
2 2 54
====
2 2 7

*/

Compilation message (stderr)

bridges.cpp: In function 'void DSU::rollback(int)':
bridges.cpp:55:28: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     while(undostack.size() > x)
      |                            ^

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