Submission #157979

#	Time	Username	Problem	Language	Result	Execution time	Memory
157979		combi1k1	Bridges (APIO19_bridges)	C++14	46 / 100	3089 ms	12504 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

const int   N   = 1e5 + 5;
const int   B   = 250;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define sz(x)   x.size()
#define X       first
#define Y       second

typedef pair<int,int>   ii;
typedef pair<int,ii>    pii;
typedef vector<pii>     vi;

struct Edge {
  int x, y;
  int w, i;
  bool operator < (const Edge &a) const   {
    return  ii(w,i) > ii(a.w,a.i);
  }
};
struct Ques {
  int mas, ver, idx;
  bool operator < (const Ques& a) const   {
    return  mas > a.mas;
  }
};

bool uV[N], uE[N];

namespace DSU   {
  int p[N], s[N];
  int lead(int x) {
    return  p[x] == x ? x : p[x] = lead(p[x]);
  }
  int join(int x,int y)   {
    x = lead(x);
    y = lead(y);
    if (x == y) return  0;
    if (uV[y])  swap(x,y);
    if (uV[x] == uV[y] && s[x] < s[y])
      swap(x,y);
    p[y] = x;
    s[x] += s[y];
    return  1;
  }
};

set<Edge>   E;
int n, m;
int x[N], y[N], w[N];

void calc(vector<Ques>  qr) {
  iota(DSU::p + 1,DSU::p + 1 + n,1);
  fill(DSU::s + 1,DSU::s + 1 + n,1);
  fill(uV + 1,uV + 1 + n,0);
  fill(uE + 1,uE + 1 + m,0);
  vector<Ques>    sta;
  vector<int>     vx;
  vector<int>     ed;
  map<int,vi> mp;
  for(Ques t : qr)    {
    if(!t.idx)  uE[t.ver] = 1,  uV[x[t.ver]] = uV[y[t.ver]] = 1;
    else        sta.pb(t),      uV[t.ver] = 1;
  }
  for(int i = 1 ; i <= n ; ++i)   if (uV[i])  vx.pb(i);
  for(int i = 1 ; i <= m ; ++i)   if (uE[i])  ed.pb(i);
  sort(all(sta));
  auto it = E.begin();
  for(Ques t : sta)   {
    while (it != E.end() && (*it).w >= t.mas)   {
      if(!uE[(*it).i])    DSU::join((*it).x,(*it).y);
      it++;
    }
    for(int x : vx) mp[t.idx].pb(pii(x,{DSU::lead(x),DSU::s[DSU::p[x]]}));
  }
  for(Ques q : qr)    {
    if(!q.idx)  {
      Edge it = *E.find({x[q.ver],y[q.ver],w[q.ver],q.ver});
      E.erase(it);    it.w = w[q.ver] = q.mas;
      E.insert(it);   continue;
    }
    for(pii t : mp[q.idx])  DSU::p[t.X] = t.Y.X, DSU::s[t.X] = t.Y.Y;
    for(int i : ed) if (w[i] >= q.mas)
      DSU::join(x[i],y[i]);
    cout << DSU::s[DSU::lead(q.ver)] << "\n";
  }
}

int main()  {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  cin >> n >> m;

  for(int i = 1 ; i <= m ; ++i)    {
    cin >> x[i] >> y[i] >> w[i];
    E.insert({x[i],y[i],w[i],i});
  }

  int q;  cin >> q;

  vector<Ques>    v;

  for(int i = 1 ; i <= q ; ++i)   {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1) v.pb({y,x,0});
    if (t == 2) v.pb({y,x,i});
  }

  for(int i = 0 ; i < q ; i += B)
    calc(vector<Ques>(v.begin() + i,v.begin() + min(q,i + B)));
}

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