Submission #448371

#	Time	Username	Problem	Language	Result	Execution time	Memory
448371		SirCovidThe19th	Bridges (APIO19_bridges)	C++14	59 / 100	3061 ms	7292 KiB

bridges

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

#define pb push_back

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

struct trip{ int f, s, t; };
struct UF{
    int par[mx], sz[mx];
    UF(){ iota(par, par+mx, 0); fill(sz, sz+mx, 1); }
    inline int get(int i){ return par[i] == i ? i : par[i] = get(par[i]); }
    inline void mg(int a, int b){
        a = get(a); b = get(b); 
        if (a == b){ return; } if (sz[a] > sz[b]){ swap(a, b); }
        par[a] = b; sz[b] += sz[a];
    }
};

int n, m, q, res[sq]; trip E[mx]; vector<int> adj[mx], edg[sq]; bool use[mx], ch[mx];

void solve(int lim){
    vector<trip> Q; vector<int> ask, upd, noch; int p = 0; 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++;
        
        vector<int> dfs, rem; int ans = 0, cmp = dsu.get(Q[i].s); 
        dfs.pb(cmp); use[cmp] = 1; rem.pb(cmp);
        
        for (int j : edg[i]){
            int a = dsu.get(E[Q[j].s].f), b = dsu.get(E[Q[j].s].s);
            rem.pb(a); rem.pb(b); adj[a].pb(b); adj[b].pb(a);
        }
        while (!dfs.empty()){
            int curr = dfs.back(); dfs.pop_back(); ans += dsu.sz[curr];
            for (int nxt : adj[curr]) if (!use[nxt]) dfs.pb(nxt), use[nxt] = 1, rem.pb(nxt);
        }
        for (int j : rem){ use[j] = 0, adj[j].clear(); } res[i] = ans;
    }
    for (int i = 0; i < lim; i++) if (Q[i].f == 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 >> 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 function 'void solve(int)':
bridges.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         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