Submission #448374

#	Time	Username	Problem	Language	Result	Execution time	Memory
448374		SirCovidThe19th	Bridges (APIO19_bridges)	C++14	100 / 100	2326 ms	11224 KiB

bridges

#include <bits/stdc++.h>
using namespace std; 

#define pb push_back

const int mx = 1e5+5, sq = 999;

struct trip{ int f, s, t; };
struct UF{
    int par[mx], sz[mx]; vector<int> ops;
    UF(){ iota(par, par+mx, 0); fill(sz, sz+mx, 1); }
    int get(int i){ return par[i] == i ? i : get(par[i]); }
    void mg(int a, int b){
        a = get(a); b = get(b); 
        if (a == b){ return; } if (sz[a] > sz[b]){ swap(a, b); }
        ops.pb(a); par[a] = b; sz[b] += sz[a];
    }void rollBack(int x){
        while (ops.size() > x){
            int curr = ops.back(); ops.pop_back();
            sz[par[curr]] -= sz[curr]; par[curr] = curr;
        }
    }
};

int n, m, q, A[mx], B[mx], W[mx], T[sq], X[sq], Y[sq]; vector<int> edg[sq]; bool ch[mx];

void solve(int lim){
    vector<int> ask, upd, noch; int p = 0, res[lim]; UF dsu = UF();

    for (int i = 0; i < lim; i++){
        cin >> T[i] >> X[i] >> Y[i];
        if (T[i] == 1) ch[X[i]] = 1, upd.pb(i);
        else ask.pb(i);
    }
    for (int i = 1; i <= m; i++){
        if (!ch[i]) noch.pb(i);
        else ch[i] = 0;
    }

    sort(noch.begin(), noch.end(), [&](int a, int b){ return W[a] > W[b]; });
    sort(ask.begin(), ask.end(), [&](int a, int b){ return Y[a] > Y[b]; });
    
    for (int i = 0; i < lim; i++){
        if (T[i] == 1) W[X[i]] = Y[i];
        else{
            edg[i].clear(); 
            for (int j : upd) if (W[X[j]] >= Y[i]) edg[i].push_back(X[j]);
        }
    }
    for (int i : ask){
        while (p < noch.size() and W[noch[p]] >= Y[i]) dsu.mg(A[noch[p]], B[noch[p]]), p++;
        int prevS = dsu.ops.size();
        for (int j : edg[i]) dsu.mg(A[j], B[j]);
        res[i] = dsu.sz[dsu.get(X[i])];
        dsu.rollBack(prevS);
    }
    for (int i = 0; i < lim; i++) if (T[i] == 2) cout<<res[i]<<endl;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> A[i] >> B[i] >> W[i];
    cin >> q; 
    for (int i = 0; i < q; i += sq) solve(min(sq, q-i));
}
 

Compilation message (stderr)

bridges.cpp: In member function 'void UF::rollBack(int)':
bridges.cpp:18:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |         while (ops.size() > x){
      |                ~~~~~~~~~~~^~~
bridges.cpp: In function 'void solve(int)':
bridges.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         while (p < noch.size() and W[noch[p]] >= Y[i]) dsu.mg(A[noch[p]], B[noch[p]]), p++;
      |                ~~^~~~~~~~~~~~~

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