Submission #811201

#	Time	Username	Problem	Language	Result	Execution time	Memory
811201		Skywk	Bridges (APIO19_bridges)	C++17	59 / 100	3064 ms	71076 KiB

bridges

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

const int MAXM = 1e5;
const int MAXN = 5e4;
struct DSU{
private:
    int id[MAXN+1];
public:
    int sz[MAXN+1];
    stack<int> rollback;
    void set(int n){
        iota(id, id + n, 0);
        fill(sz, sz + n, 1);
    }
    int findset(int u){
        while(id[u] != u) u = id[u];
        return u;
    }
    void joinset(int u, int v){
        int pu = findset(u), pv = findset(v);
        if(pu == pv) return;
        if(sz[pu] > sz[pv]) swap(pu, pv);
        rollback.push(pu);
        id[pu] = pv;
        sz[pv] += sz[pu];
    }
    void disjoint(int x){
        while(rollback.size() > x){
            int u = rollback.top();
            rollback.pop();
            int v = id[u];
            sz[v] -= sz[u];
            id[u] = u;
        }
    }
    int size(int u){
        return sz[findset(u)];
    }
}dsu;
struct edge{
    int u, v, w;
};
edge ed[MAXM+1];
const int MAXQ = 1e5;
struct query{
    int t, idx, w;
};
query q[MAXQ+1];
const int block_size = 316;
int res[MAXQ+1];
vector<int> upd, ask, keep, join[block_size + 1];
bitset<MAXM+1> vis;
#define clr(arr) arr.clear(), arr.shrink_to_fit()

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

    int N, M;
    cin>> N>> M;

    for(int i=1; i<=M; i++){
        int u, v, w;
        cin>> u>> v>> w;
        ed[i] = {u, v, w};
    }

    int Q;
    cin>> Q;
    for(int i=0; i<Q; i++){
        int t, idx, w;
        cin>> t>> idx>> w;
        q[i] = {t, idx, w};
    }

    for(int ini = 0, fin; ini < Q; ini = fin + 1){
        fin = min(Q - 1, ini + block_size);
        clr(upd), clr(ask), clr(keep);
        vis.reset();
        for(int i=ini; i<=fin; i++){
            if(q[i].t == 1){
                vis[q[i].idx] = 1;
            }
            else ask.push_back(i);
        }
        for(int i=1; i<=M; i++){
            if(!vis[i]) keep.push_back(i);
            else upd.push_back(i);
        }
        for(int i=ini; i<=fin; i++){
            if(q[i].t == 1){
                ed[q[i].idx].w = q[i].w;
            }
            else{
                clr(join[i - ini]);
                for(auto idx : upd){
                    if(ed[idx].w >= q[i].w) join[i - ini].push_back(idx);
                }
            }
        }
        sort(keep.begin(), keep.end(), [&](int x, int y){
            return ed[x].w > ed[y].w;
        });
        sort(ask.begin(), ask.end(), [&](int x, int y){
            return q[x].w > q[y].w;
        });
        int ptr = 0;
        dsu.set(N+1);
        for(auto i : ask){
            while(ptr < keep.size() && ed[keep[ptr]].w >= q[i].w){
                dsu.joinset(ed[keep[ptr]].u, ed[keep[ptr]].v);
                ptr++;
            }
            int curr_sz = dsu.rollback.size();
            for(auto j : join[i - ini]) dsu.joinset(ed[j].u, ed[j].v);
            res[i] = dsu.size(q[i].idx);
            dsu.disjoint(curr_sz);
        }
    }
    for(int i=0; i<Q; i++) if(res[i] > 0) cout<< res[i]<< '\n';
    return 0; 
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::disjoint(int)':
bridges.cpp:30:31: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |         while(rollback.size() > x){
      |               ~~~~~~~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:112:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             while(ptr < keep.size() && ed[keep[ptr]].w >= q[i].w){
      |                   ~~~~^~~~~~~~~~~~~

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