Submission #493918

#	Time	Username	Problem	Language	Result	Execution time	Memory
493918		cadmiumsky	Bridges (APIO19_bridges)	C++14	0 / 100	3071 ms	10364 KiB

bridges

#include <iostream>
#include <tuple>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <stack>
#include <vector>
#include <cmath>
 
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2")
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 || (type%2==camsus.type%2 && 
        tuple<int,int,int,int>{type, x, w, ind} < tuple<int,int,int,int>{camsus.type, camsus.x, camsus.w, camsus.ind}  )));
  }
  bool operator == (const query& camsus) const {
    return tuple<int,int,int,int>{type, x, w, ind} == tuple<int,int,int,int>{camsus.type, camsus.x, camsus.w, camsus.ind};
  }
}initq[qmax];
 
unordered_set< int > used;
vector< query > inupd,qs,here;
 
static vector<query> merge(vector<query> a, vector<query> b) {
  vector<query> temp;
  while(a.size() && b.size()) {
    if(b[0]<a[0])
      swap(a,b);
    temp.push_back(a[0]);
    a.erase(a.begin());
  }
  copy(b.begin(),b.end(),back_inserter(temp));
  return temp;
}
 
static void solve(int l, int r) {
  DSU::rollback(0);
  if(used.size()!=0)
    used.erase(used.begin(),used.end());
  if(here.size())
    here.erase(here.begin(),here.end());
  if(inupd.size())
    inupd.erase(inupd.begin(),inupd.end());
  for(int i = l; i <= r; i++) {
    if(initq[i].type == 1) {
      used.insert(initq[i].x);
      inupd.push_back(initq[i]);
    }
    else {
      here.push_back(initq[i]);
    } 
  }
  sort(inupd.begin(),inupd.end());
  sort(here.begin(),here.end());
  int ptr=0;
  for(int i = 0; i < qs.size(); i++) {
    if(used.count(qs[i].x))
      qs.erase(qs.begin()+i),i--;
  }
  //for(auto x:qs)
    //cout << "remain" <<x.type <<' '<< x.x << ' '<< x.w <<'\n';
  qs=merge(qs,here);
  //cout << "=====";
  //for(auto x:qs)
    //cout << "remain" <<x.type <<' '<< x.x << ' '<< x.w <<'\n';
  for(auto x:qs) {
    if(x.type == 3) {
      if(used.count(x.x)==0)
        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);
    }
  }
  for(int i = 0; i < qs.size(); i++) {
    if(qs[i].type == 2) {
      qs.erase(qs.begin()+i);
      i--;
    } 
  }
  
  for(int i = l; i <= r; i++) {
    if(initq[i].type==1) {
      prevweight[initq[i].x] = weight[initq[i].x] = initq[i].w;
    }
  }
  for(auto &x:inupd) {
    x.w=weight[x.x];
    x.type=3;
    //cout << ";-;" << x.x << ' '<< x.w <<'\n';
  }
  sort(inupd.begin(),inupd.end());
  qs=merge(qs,inupd);
  
  //cout << '\n';
  //cout << '\n';
}
static void fix(int l, int r) {
  
  return;
}
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  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);
    }
  }
  for(int i = 0; i < m; i++) {
      //cerr << i<< ' ' << weight[i] <<'\n';
    qs.push_back(query{3, i, weight[i], 0});
  }
  sort(qs.begin(),qs.end());
  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=-1;
  while(l < q) {
    r=min(q - 1, r + buck);
    solve(l,r);
    fix(l,r);
    l += buck;
  }
  for (int i = 0; i < q; i++) {
    if(initq[i].type == 2)
      cout << rez[i] << '\n';
  }
}

Compilation message (stderr)

bridges.cpp: In function 'void DSU::rollback(int)':
bridges.cpp:59: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]
   59 |     while(undostack.size() > x)
      |                            ^
bridges.cpp: In function 'void solve(int, int)':
bridges.cpp:119:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   for(int i = 0; i < qs.size(); i++) {
      |                  ~~^~~~~~~~~~~
bridges.cpp:155:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |   for(int i = 0; i < qs.size(); i++) {
      |                  ~~^~~~~~~~~~~
bridges.cpp:118:7: warning: unused variable 'ptr' [-Wunused-variable]
  118 |   int ptr=0;
      |       ^~~

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