Submission #1130239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130239		Hamed_Ghaffari	Bridges (APIO19_bridges)	C++20	73 / 100	3045 ms	57572 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;


struct DSU {
    int par[MXN], sz[MXN];
    int Find(int v) {
        return v==par[v] ? v : par[v]=Find(par[v]);
    }
    inline void Union(int u, int v) {
        if((u=Find(u))==(v=Find(v))) return;
        if(sz[u]<sz[v]) swap(u,v);
        sz[par[v]=u] += sz[v];
    }
} dsu, dsu_tmp;

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;
        fill(in_block, in_block+m, 0);
        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]; });
        sort(all(que), [&](int i, int j) { return Q[i][2]>Q[j][2]; });
        iota(dsu.par, dsu.par+n, 0);
        fill(dsu.sz, dsu.sz+n, 1);
        iota(dsu_tmp.par, dsu_tmp.par+n, 0);
        fill(dsu_tmp.sz, dsu_tmp.sz+n, 1);
        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]]) dsu.Union(U[ord[ptr]], V[ord[ptr]]);
                ptr++;
            }
            vector<int> vec = {dsu.Find(Q[i][1])};
            for(int e : BE[i])
                vec.pb(dsu.Find(U[e])),
                vec.pb(dsu.Find(V[e]));
            for(int v : vec)
                dsu_tmp.sz[v]=dsu.sz[v];
            for(int e : BE[i])
                dsu_tmp.Union(dsu.Find(U[e]), dsu.Find(V[e]));
            ans[i] = dsu_tmp.sz[dsu_tmp.Find(dsu.Find(Q[i][1]))];
            for(int v : vec)
                dsu_tmp.par[v] = v;
        }
        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: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27