Submission #1182957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182957		peter-007	Bridges (APIO19_bridges)	C++20	0 / 100	3096 ms	31000 KiB

bridges

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct dsu
{
    vector<int>parent,sz;
    dsu(int size)
    {
        parent.resize(size),sz.resize(size);
        for(int i=0;i<size;i++)parent[i]=i,sz[i]=1;
    }
    int find_parent(int x)
    {
        if(x==parent[x])return x;
        return parent[x]=find_parent(parent[x]);
    }
    void align(int a,int b)
    {
        a=find_parent(a),b=find_parent(b);
        if(a==b)return;
        if(sz[a]<sz[b])swap(a,b);
        sz[a]+=sz[b],parent[b]=a;
    }
};
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n,m;
  cin>>n>>m;
  vector<pair<int,int>>cur_edge(m);
  vector<pair<int,int>>edge_info;
  vector<vector<int>>edges;
  vector<int>compress;
  for(int i=0;i<m;i++)
  {
      int u,v;
      cin>>u>>v>>cur_edge[i].second;
      compress.push_back(cur_edge[i].second);
      cur_edge[i].first=0;
      u--,v--;
      edge_info.push_back({u,v});
  }
  int q;
  cin>>q;
  vector<vector<int>>queries(q,vector<int>(3));
  for(auto &x:queries)
  {
      for(auto &y:x)cin>>y;
      compress.push_back(x[2]);
      x[1]--;
  }
  sort(compress.begin(),compress.end());
  compress.erase(unique(compress.begin(),compress.end()),compress.end());
  for(auto &x:cur_edge)x.second=lower_bound(compress.begin(),compress.end(),x.second)-compress.begin();
  for(auto &x:queries)x[2]=lower_bound(compress.begin(),compress.end(),x[2])-compress.begin();
  for(int i=0;i<q;i++)
  {
      if(queries[i][0]==2)continue;
      edges.push_back({cur_edge[queries[i][1]].first,i-1,cur_edge[queries[i][1]].second,queries[i][1]});
      cur_edge[queries[i][1]]={i,queries[i][2]};
  }
  for(int i=0;i<m;i++)edges.push_back({cur_edge[i].first,q-1,cur_edge[i].second,i});
  int block_size=max(1,(int)sqrt(q));
  vector<vector<int>>base_push(compress.size());
  vector<vector<int>>solve_queries(compress.size());
  vector<int>weird_idx;
  vector<int>ans(q);
  for(int i=0;i<q;i+=block_size)
  {
      int r=min(q,i+block_size)-1;
      for(int j=0;j<edges.size();j++)
      {
          if(edges[j][0]>=i&&edges[j][0]<=r||edges[j][1]>=i&&edges[j][1]<=r)weird_idx.push_back(j);
          else if(edges[j][0]<=i&&edges[j][1]>=r)base_push[edges[j][2]].push_back(edges[j][3]);
      }
      for(int j=i;j<=r;j++)
      {
          if(queries[j][0]==1)continue;
          solve_queries[queries[j][2]].push_back(j);
      }
      dsu ds(n),cur_s(n);
      vector<int>push(n);
      for(int it=compress.size()-1;it>=0;it--)
      {
          for(auto &x:base_push[it])ds.align(edge_info[x].first,edge_info[x].second);
          for(auto &x:solve_queries[it])
          {
              for(auto &y:weird_idx)
              {
                  if(edges[y][0]<=x&&edges[y][1]>=x&&edges[y][2]>=queries[x][2])
                  {
                      int v=edges[y][3];
                      int f1=ds.find_parent(edge_info[v].first),f2=ds.find_parent(edge_info[v].second);
                      push[f1]=2,push[f2]=2;
                      cur_s.align(f1,f2);
                  }
              }
              if(!push[ds.find_parent(queries[x][1])])ans[x]=ds.sz[ds.find_parent(queries[x][1])];
              for(auto &y:weird_idx)
              {
                  if(edges[y][0]<=x&&edges[y][1]>=x&&edges[y][2]>=queries[x][2])
                  {
                      int v=edges[y][3];
                      int f1=ds.find_parent(edge_info[v].first),f2=ds.find_parent(edge_info[v].second);
                      if(push[f1]==2&&cur_s.find_parent(f1)==cur_s.find_parent(queries[x][1]))ans[x]+=ds.sz[f1],push[f1]=1;
                      if(push[f2]==2&&cur_s.find_parent(f2)==cur_s.find_parent(queries[x][1]))ans[x]+=ds.sz[f2],push[f2]=1;
                  }
              }
              for(auto &y:weird_idx)
              {
                  if(edges[y][0]<=x&&edges[y][1]>=x&&edges[y][2]>=queries[x][2])
                  {
                      int v=edges[y][3];
                      int f1=ds.find_parent(edge_info[v].first),f2=ds.find_parent(edge_info[v].second);
                      if(push[f1]==1)cur_s.sz[f1]=1,cur_s.parent[f1]=f1,push[f1]=0;
                      if(push[f2]==1)cur_s.sz[f2]=1,cur_s.parent[f2]=f2,push[f2]=0;
                  }
              }
          }
      }
      for(int i=0;i<compress.size();i++)base_push[i].clear(),solve_queries[i].clear();
      weird_idx.clear();
  }
  for(int i=0;i<q;i++)
  {
      if(queries[i][0]==1)continue;
      cout<<ans[i]<<endl;
  }
}

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