Submission #1261292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261292		minhpk	Bridges (APIO19_bridges)	C++20	59 / 100	3091 ms	411136 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
int a,b;
struct node{
     int x,y,t;
};
node z[100005];
set<pair<int,int>> s;
int block=320;
struct query{
       int c,x,y;
};
query q[100005];
vector<pair<int,int>> pre[100005];

bool cmp(pair<int,int> a,pair<int,int> b){
     return a.second>b.second;
}
bool cmp1(node a,node b){
     return a.y>b.y;
}
int res[100005];
int curpos;
int id[100005];

struct dsu{
     int par[100005];
     int sz[100005];
     stack<pair<int,int>> st;
     void init(){
         for (int i=1;i<=a;i++){
              par[i]=i;
              sz[i]=1;
         }
         while (st.size()){
               st.pop();
         }
     }
     int find(int u){
         if(par[u]==u){
            return u;
         }
         return find(par[u]);
     }
     void join(int x,int y){
         x=find(x);
         y=find(y);
         if (x==y){
             st.push({-1,-1});
             return;
         }
         if (sz[x]<sz[y]){
             swap(x,y);
         }
         par[y]=x;
         sz[x]+=sz[y];
         st.push({x,y});
     }
     void rollback(){
          auto [x,y]=st.top();
          st.pop();
          if (x==-1){
              return;
          }
          sz[x]-=sz[y];
          par[y]=y;
     }
};
dsu d;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=b;i++){
         cin >> z[i].x >> z[i].y >> z[i].t;
         s.insert({i,z[i].t});
    }
    int sadge;
    cin >> sadge;
    for (int i=1;i<=sadge;i++){
         cin >> q[i].c >> q[i].x >> q[i].y;
         if (q[i].c==2){
             curpos++;
             id[i]=curpos;
         }
    }
    for (int t=1;t<=min(sadge,t+block-1);t+=block){
         set<pair<int,int>> s1;
         int fin=min(sadge,t+block-1);
         vector<node> pos;
         for (int i=t;i<=fin;i++){
              if (q[i].c==1){
                  auto it=s.lower_bound({q[i].x,0LL});
                  if (it->first==q[i].x){
                      s1.insert(*it);
                      s.erase(it);
                  }
              }else{
                  pos.push_back({q[i].x,q[i].y,i});
              }
         }
         sort(pos.begin(),pos.end(),cmp1);
         for (int i=t;i<=fin;i++){
              if (q[i].c==1){
                  auto it=s1.lower_bound({q[i].x,0LL});
                  s1.erase(it);
                  s1.insert({q[i].x,q[i].y});
              }
             if (s1.size()){
                 for (auto p:s1){
                   pre[i].push_back(p);
                 } 
             } 
         }
         vector <pair<int,int>> z1;
         for (auto p:s){
              z1.push_back(p);
         }
         sort(z1.begin(),z1.end(),cmp);
         int cur=0;
         d.init();
         for (int i=0;i<pos.size();i++){
              auto [x,y,t1]=pos[i];
              while (cur<z1.size() && z1[cur].second>=y){
                     auto [u,v]=z1[cur];
                     d.join(z[u].x,z[u].y);
                     cur++;
              }
              for (auto p:pre[t1]){
                   if (p.second>=y){
                       d.join(z[p.first].x,z[p.first].y);
                   }
              }
              res[id[t1]]=d.sz[d.find(x)];
              for (auto p:pre[t1]){
                   if (p.second>=y){
                       d.rollback();
                   }
              }
         }
        if (s1.size()){
            for (auto p:s1){
              s.insert(p);
            }  
        } 
         s1.clear();
         pos.clear();
         z1.clear();
    }
    for (int i=1;i<=curpos;i++){
         cout << res[i] << "\n";
    }
    return 0;
}

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