Submission #973546

#	Time	Username	Problem	Language	Result	Execution time	Memory
973546		vjudge1	Bridges (APIO19_bridges)	C++14	73 / 100	3096 ms	12424 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

struct DSU{
   int n;
   vector<int> lab;
   void init(int _n){
      n=_n;
      lab.assign(n+1, -1);
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   void union_sets(int u, int v){
      u=find_set(u), v=find_set(v);
      if (u!=v){
         if (lab[u]>lab[v]) swap(u, v);
         lab[u]+=lab[v];
         lab[v]=u;
      }
   }
} dsu;

struct Edge{
   int u, v, w;
   Edge (int _u=0, int _v=0, int _w=0){
      u=_u, v=_v, w=_w;
   }
};

struct Query{
   int type, x, y;
   Query (int _type=0, int _x=0, int _y=0){
      type=_type, x=_x, y=_y;
   }
};

const int N=1e5+10, S=320;
Edge e[N];
int idx[N], ans[N];
int n, m, q;
int used[N];
Query qq[N];
vector<int> g[N];
int w[N];
int vis[N];

void dfs(int u, int &cnt){
   vis[u]=1; cnt-=dsu.lab[u];
   for (int v:g[u]) if (!vis[v]) dfs(v, cnt);
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   for (int i=1; i<=m; ++i){
      cin >> e[i].u >> e[i].v >> e[i].w;
   }
   cin >> q;
   for (int i=1; i<=q; ++i){
      cin >> qq[i].type >> qq[i].x >> qq[i].y;
   }
   iota(idx, idx+m+1, 0);
   for (int l=1, r=S; l<=q; l+=S, r+=S){
      r=min(r, q);
      vector<int> vv;
      vector<int> edge;
      for (int i=l; i<=r; ++i){
         if (qq[i].type==1){
            used[qq[i].x]=1;
            edge.push_back(qq[i].x);
         }else vv.push_back(i);
      }
      sort(idx+1, idx+m+1, [&](int x, int y){ return make_pair(!used[x], e[x].w)>make_pair(!used[y], e[y].w); });
      sort(vv.begin(), vv.end(), [&](int x, int y){ return qq[x].y>qq[y].y; });
      dsu.init(n);
      int id=1;
      for (int i:vv){
         while (id<=m && !used[idx[id]] && e[idx[id]].w>=qq[i].y){
            dsu.union_sets(e[idx[id]].u, e[idx[id]].v);
            ++id;
         }
         for (int j:edge) w[j]=e[j].w;
         for (int j=l; j<=i; ++j) if (qq[j].type==1) w[qq[j].x]=qq[j].y;
         vector<int> vertex;
         for (int j:edge) if (w[j]>=qq[i].y){
            int cc1=dsu.find_set(e[j].u), cc2=dsu.find_set(e[j].v);
            if (cc1!=cc2){
               vertex.push_back(cc1); vertex.push_back(cc2);
               g[cc1].push_back(cc2);
               g[cc2].push_back(cc1);
            }
         }
         dfs(dsu.find_set(qq[i].x), ans[i]);
         vis[dsu.find_set(qq[i].x)]=0;
         for (int j:vertex) g[j].clear(), vis[j]=0;
      }
      for (int i=l; i<=r; ++i) if (qq[i].type==1) e[qq[i].x].w=qq[i].y, used[qq[i].x]=0;
   }
   for (int i=1; i<=q; ++i) if (qq[i].type==2) cout << ans[i] << '\n';
   return 0;
}

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