Submission #1261290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261290		minhpk	Bridges (APIO19_bridges)	C++20	59 / 100	3091 ms	411220 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.empty()) 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 pr = st.top(); st.pop();
        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){
        set<pair<int,int>> s1;
        int fin = min(sadge, t + block - 1);
        vector<node> pos;
        for (int i=t;i<=fin;i++) pre[i].clear();
        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});
            }
            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);
        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;
            int y = pos[i].y;
            int 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 : pre[t1]){
                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 : pre[t1]){
                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: 0 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27