Submission #994406

#	Time	Username	Problem	Language	Result	Execution time	Memory
994406		yeediot	Bridges (APIO19_bridges)	C++17	100 / 100	976 ms	9348 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define tiii tuple<int, int, int>
#define toi_is_so_de ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int mxn = 5e4+5, mxm = 1e5+5, siz = sqrt(mxm);
int n, m, q, v[mxm], id[mxm], ans[mxm], op[mxm], a[mxm], b[mxm], c[mxm], x[mxm], y[mxm], ord[mxm], nword[mxm];
bool vis[mxm], changed[mxm];
struct DSU {
    int to[mxn], num[mxn];
    vector<int>adj[mxn];
    bool vs[mxn];
    void init(int n){
        for(int i = 1; i <= n; i++){
            to[i] = i;
            num[i] = 1;
        }
    }
    int find(int x){
        return x == to[x] ? x : to[x] = find(to[x]);
    }
    bool merge(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return false;
        if(num[x] < num[y])swap(x, y);
        to[y] = x;
        num[x] += num[y];
        return true;
    }
    int dfs(int v){
        int res = 0;
        vs[v] = 1;
        for(auto u : adj[v]){
            if(!vs[u]) res += dfs(u);
        }
        return res+num[v];
    }
}d;
signed main(){
    toi_is_so_de;
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> a[i] >> b[i] >> c[i];
        ord[i] = i;
    }
    cin >> q;
    for(int i=1;i<=q;i++){
        cin >> op[i] >> x[i] >> y[i];
    }
    sort(ord+1, ord+1+m, [&](int i, int j){return c[i] > c[j];});
    for(int i=1;i<=q;i+=siz){
        d.init(n);
        vector<int> qres, temp;
        for(int j=min(q, i+siz-1);j>=i;j--){
            if(op[j] == 1){
                changed[x[j]] = 1;
                temp.pb(x[j]);
            }
            else{
                qres.pb(j);
            }
        }
        sort(all(temp));
        temp.resize(unique(all(temp))-temp.begin());
        int pos = 0;
        sort(all(qres), [&](int i, int j){return y[i] > y[j];});
        for(auto t : qres){
            while(pos+1 <= m and c[ord[pos+1]] >= y[t]){
                pos++;
                if(changed[ord[pos]] == 0) d.merge(a[ord[pos]], b[ord[pos]]);
            }
            //int ro = sz(d.temp);
            vector<int>del;
            for(int j=t;j>=i;j--){
                if(op[j] == 2 or vis[x[j]])continue;
                vis[x[j]] = 1;
                if(y[j] >= y[t]){
                    int l = d.find(a[x[j]]), r = d.find(b[x[j]]);
                    d.adj[l].pb(r);
                    d.adj[r].pb(l);
                    del.pb(l);
                    del.pb(r);
                }
            }
            for(auto x : temp){
                if(vis[x]) vis[x] = 0;
                else if(c[x] >= y[t]){
                    int l = d.find(a[x]), r = d.find(b[x]);
                    d.adj[l].pb(r);
                    d.adj[r].pb(l);
                    del.pb(l);
                    del.pb(r);
                }
            }
            int g = d.find(x[t]);
            ans[t] = d.dfs(g);
            del.pb(g);
            for(auto k:del){
                d.adj[k].clear();
                d.vs[k] = 0;
            }
        }
        for(int j=i;j<=min(q,i+siz-1);j++){
            if(op[j] == 1){
                c[x[j]] = y[j];
            }
        }
        sort(all(temp), [&](int j, int k){return c[j] > c[k];});
        int cr = 0, cnt = 0;
        for(int j=1;j<=m;j++){
            if(changed[ord[j]])continue;
            while(cr < sz(temp) and c[ord[j]] < c[temp[cr]]){
                nword[++cnt] = temp[cr++];
            }
            nword[++cnt] = ord[j];
        }
        while(cr < sz(temp)){
            nword[++cnt] = temp[cr++];
        }
        for(int j=1;j<=m;j++){
            ord[j] = nword[j];
        }
        for(int j=i;j<=min(q,i+siz-1);j++){
            if(op[j] == 1){
                changed[x[j]] = 0;
            }
        }
    }
    for(int i=1;i<=q;i++){
        if(ans[i]) cout<< ans[i] << '\n';
    }
}

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