Submission #1162999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162999		Otalp	Bridges (APIO19_bridges)	C++20	59 / 100	3095 ms	25964 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define unm unordered_map

const ll mod = 1e9 + 7;
const int MAXN = 2e5 + 5;
const int MAXA = 2e5 + 5;

vector<int> q[200100], dq[200100];
int fat = 350;
int us[200100], dus[200100], ans[200100];

struct DSU{
    int p[50100], sz[50100];
    void build(int n){
        for(int i=1; i<=n; i++){
            p[i] = i;
            sz[i] = 1;
        }
    }
    int get(int a){
        if(p[a] == a) return a;
        return p[a] = get(p[a]);
    }
    void un(int a, int b){
        a = get(a);
        b = get(b);
        if(a == b) return;
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        p[b] = a;
    }
};

void solve(){
    int n, m;
    cin>>n>>m;
    set<pii> dq;
    for(int i=1; i<=m; i++){
        int l, r, x;
        cin>>l>>r>>x;
        x = -x;
        dq.insert({x, i});
        q[i] = {l, r, x};
    }
    vector<vector<int> > z;
    int t = 0;
    cin>>t;
    fat = sqrt(t);
    // fat = 1;
    for(int i=0; i<t; i++){
        int l, r, x;
        cin>>l>>r>>x;
        x = -x;
        z.pb({l, r, x});
    }
    DSU dds, ds;
    dds.build(n);
    for(int t=0; t<z.size(); t+=fat){
        int ngr = min((int)z.size(), t + fat);
        vector<vector<int>> h;
        vector<int> use;
        for(int i=t; i<ngr; i++){
            if(z[i][0] == 2){
                h.pb({z[i][2], z[i][1], i});
            }
            else{
                if(!us[z[i][1]])use.pb(z[i][1]);
                us[z[i][1]] = 1;
            }
        }
        sort(h.begin(), h.end());
        vector<int> d;
        for(auto it: dq){
            if(us[it.ss]) continue;
            d.pb(it.ss);
        }
        int ls=-1;
        ds.build(n);
        for(auto g: h){
            // cout<<g[0]<<' '<<g[1]<<' '<<g[2]<<'\n';
            while(ls + 1 < d.size() and q[d[ls + 1]][2] <= g[0]){
                ls++;
                // cout<<q[d[ls]][0]<<' '<<q[d[ls]][1]<<' '<<q[d[ls]][2]<<'\n';
                ds.un(q[d[ls]][0], q[d[ls]][1]);
            }
            vector<int> dd;
            for(int i=g[2]; i>=t; i--){
                if(z[i][0] == 2) continue;
                if(dus[z[i][1]]) continue;
                dus[z[i][1]] = 1;
                if(z[i][2] <= g[0]) dd.pb(z[i][1]);
            }
            for(int to: use){
                if(!dus[to] and q[to][2] <= g[0]) dd.pb(to);
            }
            int res = 0;
            int v = ds.get(g[1]);
            for(int x: dd){
                int l = ds.get(q[x][0]), r=ds.get(q[x][1]);
                dds.sz[l] = ds.sz[l];
                dds.sz[r] = ds.sz[r];
            }
            dds.sz[v] = ds.sz[v];
            for(int x: dd){
                int l = ds.get(q[x][0]), r=ds.get(q[x][1]);
                dds.un(l, r);
                // cout<<l<<' '<<r<<'\n';
            }
            res = dds.sz[dds.get(v)];
            ans[g[2]] = res;
            for(int x: dd){
                int l = ds.get(q[x][0]), r=ds.get(q[x][1]);
                dds.sz[l] = 1;
                dds.p[l] = l;
                dds.sz[r] = 1;
                dds.p[r] = r;
            }
            dds.sz[v] = 1;
            dds.p[v] = v;
            for(int i=g[2]; i>=t; i--){
                dus[z[i][1]] = 0;
            }
        }
        for(int i=t; i<ngr; i++){
            if(z[i][0] == 2) continue;
            int l = z[i][1], x = z[i][2];
            us[z[i][1]] = 0;
            dq.erase({q[l][2], l});
            q[l][2] = x;
            dq.insert({x, l});
        }
    }
    for(int i=0; i<z.size(); i++){
        if(z[i][0] == 2){
            cout<<ans[i]<<'\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout<<'\n';
    }
}

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