Submission #1261305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261305		minhpk	Bridges (APIO19_bridges)	C++20	100 / 100	2211 ms	16076 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=750;
struct query{ int c,x,y; };
query q[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=0;
int id[100005];
struct dsu{
    int par[100005];
    int sz[100005];
    vector<pair<int,int>> st;
    void init(){
        for (int i=1;i<=a;i++){ par[i]=i; sz[i]=1; }
        st.clear();
    }
    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_back({-1,-1}); return; }
        if (sz[x]<sz[y]) swap(x,y);
        par[y]=x;
        sz[x]+=sz[y];
        st.push_back({x,y});
    }
    void rollback(){
        auto pr=st.back(); st.pop_back();
        int x=pr.first, y=pr.second;
        if (x==-1) return;
        sz[x]-=sz[y];
        par[y]=y;
    }
} d;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin>>a>>b)) return 0;
    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;
    curpos=0;
    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<=sadge;t+=block){
        int fin=min(sadge,t+block-1);
        set<pair<int,int>> s1;
        vector<node> pos;
        pos.reserve(fin-t+1);
        vector<vector<pair<int,int>>> preBlock(fin-t+1);
        for (int i=t;i<=fin;i++){
            if (q[i].c==1){
                auto it=s.lower_bound({q[i].x,INT_MIN});
                if (it!=s.end() && it->first==q[i].x){
                    s1.insert(*it);
                    s.erase(it);
                }
            } else {
                pos.push_back({q[i].x,q[i].y,i});
            }
        }
        for (int i=t;i<=fin;i++){
            if (q[i].c==1){
                auto it=s1.lower_bound({q[i].x,INT_MIN});
                if (it!=s1.end() && it->first==q[i].x) s1.erase(it);
                s1.insert({q[i].x,q[i].y});
            }
            if (!s1.empty()){
                for (auto &p:s1) preBlock[i-t].push_back(p);
            }
        }
        vector<pair<int,int>> z1;
        z1.reserve(s.size());
        for (auto &p:s) z1.push_back(p);
        sort(z1.begin(),z1.end(),cmp);
        sort(pos.begin(),pos.end(),cmp1);
        int cur=0;
        d.init();
        for (int i=0;i<(int)pos.size();i++){
            int x=pos[i].x, y=pos[i].y, t1=pos[i].t;
            while (cur<(int)z1.size() && z1[cur].second>=y){
                int uidx=z1[cur].first;
                d.join(z[uidx].x,z[uidx].y);
                cur++;
            }
            for (auto &p:preBlock[t1-t]){
                if (p.second>=y){
                    int uidx=p.first;
                    d.join(z[uidx].x,z[uidx].y);
                }
            }
            res[id[t1]]=d.sz[d.find(x)];
            for (auto &p:preBlock[t1-t]){
                if (p.second>=y) d.rollback();
            }
        }
        for (auto &p:s1) s.insert(p);
    }
    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: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27