Submission #997027

#	Time	Username	Problem	Language	Result	Execution time	Memory
997027		star	Bridges (APIO19_bridges)	C++14	100 / 100	1434 ms	58424 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define starburst ios::sync_with_stdio(0), cin.tie(0)
#define N 100005
#define B 1000
#define pb push_back
#define all(x) x.begin(),x.end()
int n, m, q;
int u[N], v[N], w[N];
int t[N], x[N], y[N];
bool changed[N];
vector<int> edge[B]; // edges should be connected
int ans[N];
stack<int> k; // record dsu and enable rollback
int siz[N], parent[N];
void reset(){
    for (int i=1;i<=n;i++){
        parent[i]=i; // every node
        siz[i]=1; // size of connected components
    }
}
inline int fiind(int x){
    if (parent[x]==x) return x;
    return fiind(parent[x]);
}
void join(int a, int b){
    int r1=fiind(a), r2=fiind(b);
    if (r1==r2) return;
    if (siz[r1]>siz[r2]) swap(r1,r2);
    k.push(r1); // record the node which was joined by another
    siz[r2]+=siz[r1];
    parent[r1]=parent[r2];
    return;
}
void rollback(int x){
    while (k.size()>x){ // rollback until size==x
        int it=k.top();
        k.pop();
        siz[parent[it]]-=siz[it];
        parent[it]=it;
    }
}
signed main(){
    starburst;
    cin >> n >> m;
    for (int i=1;i<=m;i++) cin >> u[i] >> v[i] >> w[i];
    cin >> q;
    for (int i=1;i<=q;i++) cin >> t[i] >> x[i] >> y[i];

    for (int l=1;l<=q;l+=B){ // divide into a few blocks
        int r=min(q, l+B-1); // r=l+B-1 but r should <=q
        reset();
        for (int i=1;i<=m;i++) changed[i]=0;
        vector<int> ask, upd, unchanged;
        for (int i=l;i<=r;i++){
            if (t[i]==1){ // update
                changed[x[i]]=1;
                upd.pb(i);
            }
            else ask.pb(i);
        }
        for (int i=1;i<=m;i++) if (!changed[i]) unchanged.pb(i);
        for (int i=l;i<=r;i++){
            if (t[i]==1) w[x[i]]=y[i]; // update
            else {
                edge[i-l].clear();
                for (int j:upd){
                    // join the edges which are satisfied
                    if (w[x[j]]>=y[i]) edge[i-l].pb(x[j]);
                }
            }
        }
        //sort ask by y, decreasing
        sort(all(ask), [&](int a, int b){return y[a]>y[b];});
        //sort unchanged by w, decreasing
        sort(all(unchanged), [&](int a, int b){return w[a]>w[b];});
        int now=0;
        for (int i:ask){
            while (now<unchanged.size() && w[unchanged[now]]>=y[i]){
                // join the edges
                join(u[unchanged[now]],v[unchanged[now]]);
                now++;
            }
            int nowsiz=k.size();
            for (int j:edge[i-l]) join(u[j],v[j]);
            // count the size of connected components
            ans[i]=siz[fiind(x[i])];
            rollback(nowsiz);
        }
    }
    for (int i=1;i<=q;i++) if (t[i]==2) cout << ans[i] << endl;
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(long long int)':
bridges.cpp:38:20: warning: comparison of integer expressions of different signedness: 'std::stack<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |     while (k.size()>x){ // rollback until size==x
      |            ~~~~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:81:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             while (now<unchanged.size() && w[unchanged[now]]>=y[i]){
      |                    ~~~^~~~~~~~~~~~~~~~~

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