Submission #1130235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130235		Hamed_Ghaffari	Bridges (APIO19_bridges)	C++20	27 / 100	3116 ms	513276 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

using pii = pair<int, int>;

#define pb push_back
#define all(x) x.begin(), x.end()

const int MXN = 1e5 + 5;
const int sq  = 323;

int n;

int dsu[MXN], sz[MXN];
vector<pii> stk;
inline void DSU() {
    iota(dsu, dsu+n, 0);
    fill(sz, sz+n, 1);
    stk.clear();
}
int Find(int v) {
    return v==dsu[v] ? v : Find(dsu[v]);
}
inline void Union(int u, int v, bool save=0) {
    if((u=Find(u))==(v=Find(v))) {
        if(save) stk.pb(pii(-1, -1));
        return;
    }
    if(sz[u]<sz[v]) swap(u,v);
    sz[dsu[v]=u] += sz[v];
    if(save) stk.pb(pii(u, v));
}
inline void Undo() {
    while(!stk.empty()) {
        auto [u, v] = stk.back(); stk.pop_back();
        if(u==-1) continue;
        sz[u] -= sz[dsu[v]=v];
    }
}

int m, q, U[MXN], V[MXN], W[MXN], W_tmp[MXN], ord[MXN], ans[MXN];
bool in_block[MXN];
array<int, 3> Q[MXN];
vector<int> BE[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

    cin >> n >> m;
    for(int i=0; i<m; i++) {
        cin >> U[i] >> V[i] >> W[i];
        U[i]--;
        V[i]--;
    }
    cin >> q;
    for(int i=0; i<q; i++) {
        for(int j=0; j<3; j++)
            cin >> Q[i][j];
        Q[i][1]--;
    }
    
    iota(ord, ord+m, 0);
    for(int b=0; b*sq<q; b++) {
        vector<int> que;
        vector<int> E;
        for(int i=b*sq; i<(b+1)*sq && i<q; i++)
            if(Q[i][0]==1)
                in_block[Q[i][1]] = 1;
            else que.pb(i);
        for(int i=0; i<m; i++)
            if(in_block[i])
                E.pb(i);
        memcpy(W_tmp, W, sizeof(W_tmp));
        for(int i=b*sq; i<(b+1)*sq && i<q; i++)
            if(Q[i][0]==1) W_tmp[Q[i][1]] = Q[i][2];
            else for(int e : E)
                    if(W_tmp[e]>=Q[i][2])
                        BE[i].pb(e);
        sort(ord, ord+m, [&](int i, int j) { return W[i]>W[j]; });
        DSU();
        sort(all(que), [&](int i, int j) { return Q[i][2]>Q[j][2]; });
        int ptr=0;
        for(int i : que) {
            while(ptr<m && (in_block[ord[ptr]] || W[ord[ptr]]>=Q[i][2])) {
                if(!in_block[ord[ptr]]) Union(U[ord[ptr]], V[ord[ptr]]);
                ptr++;
            }
            for(int e : BE[i])
                Union(U[e], V[e], 1);
            ans[i] = sz[Find(Q[i][1])];
            Undo();
        }
        memcpy(W, W_tmp, sizeof(W));
    }
    for(int i=0; i<q; i++)
        if(Q[i][0]==2)
            cout << ans[i] << '\n';
    return 0;
}

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