Submission #410123

#	Time	Username	Problem	Language	Result	Execution time	Memory
410123		JerryLiu06	Bridges (APIO19_bridges)	C++17	100 / 100	2517 ms	32284 KiB

bridges

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using db = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int MOD = 1e9 + 7;
const int MX = 1e5 + 10;
const ll INF = 1e18;

const int BLOCK = 1000;

int N, M, Q; int U[MX], V[MX], W[MX]; int T[MX], X[MX], Y[MX];

bool seen[MX];

vi join[BLOCK]; int ans[MX];

int par[50010], sz[50010]; stack<int> stck;

int find(int A) { return (A == par[A]) ? A : find(par[A]); }

void onion(int A, int B) {
    A = find(A); B = find(B); if (A == B) return ; 

    if (sz[A] < sz[B]) swap(A, B); stck.push(B); par[B] = A; sz[A] += sz[B];
}
void rollback(int SZ) {
    while (sz(stck) > SZ) {
        int cur = stck.top(); stck.pop(); 

        sz[par[cur]] -= sz[cur]; par[cur] = cur;  
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> M; FOR(i, 1, M + 1) cin >> U[i] >> V[i] >> W[i]; // 1-indexed Edges
    
    cin >> Q; F0R(i, Q) cin >> T[i] >> X[i] >> Y[i];

    for (int i = 0; i < Q; i += BLOCK) {
        int j = min(Q, i + BLOCK); // Right endpoint of current block
        
        FOR(k, 1, N + 1) par[k] = k, sz[k] = 1;

        vi changed, unchanged, query;
        
        FOR(k, 1, M + 1) seen[k] = false;

        FOR(k, i, j) {
            if (T[k] == 1) { changed.pb(k); seen[X[k]] = true; }

            else { query.pb(k); }
        }
        FOR(k, 1, M + 1) if (!seen[k]) unchanged.pb(k);
        
        FOR(k, i, j) {
            if (T[k] == 1) { W[X[k]] = Y[k]; }
            
            else { 
                join[k - i].clear();
                
                EACH(C, changed) if (W[X[C]] >= Y[k]) join[k - i].pb(X[C]);
            }
        }
        
        sort(all(unchanged), [](int a, int b) { return W[a] > W[b]; });
        
        sort(all(query), [](int a, int b) { return Y[a] > Y[b]; });
        
        int ptr = 0;

        EACH(C, query) {
            while (ptr < sz(unchanged) && W[unchanged[ptr]] >= Y[C]) {
                onion(U[unchanged[ptr]], V[unchanged[ptr]]); ptr++;
            }
            int SZ = sz(stck); 

            EACH(nxt, join[C - i]) onion(U[nxt], V[nxt]);

            ans[C] = sz[find(X[C])]; rollback(SZ);
        }
    }
    F0R(i, Q) if (T[i] == 2) cout << ans[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In function 'void onion(int, int)':
bridges.cpp:66:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   66 |     if (sz[A] < sz[B]) swap(A, B); stck.push(B); par[B] = A; sz[A] += sz[B];
      |     ^~
bridges.cpp:66:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   66 |     if (sz[A] < sz[B]) swap(A, B); stck.push(B); par[B] = A; sz[A] += sz[B];
      |                                    ^~~~

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