Submission #448372

#	Time	Username	Problem	Language	Result	Execution time	Memory
448372		SirCovidThe19th	Bridges (APIO19_bridges)	C++14	59 / 100	3076 ms	4108 KiB

bridges

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

#define pb push_back

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

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; trip E[mx]; vector<int> edg[sq]; bool ch[mx];

void solve(int lim){
    vector<trip> Q; vector<int> ask, upd, noch; int p = 0, res[lim]; UF dsu = UF();
    
    for (int i = 0; i < lim; i++){
        int t, x, w; cin >> t >> x >> w; Q.pb({t, x, w});
        if (t == 1) ch[x] = 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 E[a].t > E[b].t; });
    sort(ask.begin(), ask.end(), [&](int a, int b){ return Q[a].t > Q[b].t; });
    
    for (int i = 0; i < lim; i++){
        if (Q[i].f == 1) E[Q[i].s].t = Q[i].t;
        else{
            edg[i].clear();
            for (int j : upd) if (E[Q[j].s].t >= Q[i].t) edg[i].push_back(j);
        }
    }
    for (int i : ask){
        while (p < noch.size() and E[noch[p]].t >= Q[i].t) dsu.mg(E[noch[p]].f, E[noch[p]].s), p++;
        int prevS = dsu.ops.size();
        for (int j : edg[i]) dsu.mg(E[Q[j].s].f, E[Q[j].s].s);
        res[i] = dsu.sz[dsu.get(Q[i].s)];
        dsu.rollBack(prevS);
    }
    for (int i = 0; i < lim; i++) if (Q[i].f == 2) cout<<res[i]<<endl;
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> E[i].f >> E[i].s >> E[i].t;
    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:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         while (p < noch.size() and E[noch[p]].t >= Q[i].t) dsu.mg(E[noch[p]].f, E[noch[p]].s), p++;
      |                ~~^~~~~~~~~~~~~

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