Submission #996993

#	Time	Username	Problem	Language	Result	Execution time	Memory
996993		star	Bridges (APIO19_bridges)	C++17	14 / 100	2499 ms	91516 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 50005
#define M 100005
#define B 500 // close to sqrt(M)
#define pb push_back
#define all(x) x.begin(),x.end()
int n, m, q, cnt=0, sizz;
int u[M], v[M], d[M];
int t[M], first[M], second[M];
int parent[N], siz[N];
bool change[M];
stack<int> k;
vector<int> edge[B];
int ans[M];
struct DSU{
    void reset(){
        for (int i=1;i<=n;i++) parent[i]=i, siz[i]=1;
        for (int i=1;i<=m;i++) change[i]=0;
    }
    int fiind(int x){
        if (parent[x]==x) return x;
        return parent[x]=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);
        siz[r2]+=siz[r1];
        parent[r1]=r2;
        return;
    }
    void rollback(int x){
        while (k.size()>x){
            int it=k.top();
            k.pop();
            siz[parent[it]]-=siz[it];
            parent[it]=it;
        }
    }
}dsu;
signed main(){
    starburst;
    cin >> n >> m;
    for (int i=1;i<=m;i++) cin >> u[i] >> v[i] >> d[i];
    cin >> q;
    for (int i=1;i<=q;i++) cin >> t[i] >> first[i] >> second[i];
    for (int l=1;l<=q;l+=B){
        int r=min(l+B-1, q); // r=l+B-1 && r<=q
        dsu.reset();
        vector<int> update, question;
        vector<int> nochange;
        for (int i=l;i<=r;i++){
            if (t[i]==1){
                update.pb(i);
                change[first[i]]=1;
            }
            else question.pb(i);
        }
        for (int i=1;i<=m;i++) if (!change[i]) nochange.pb(i);
        for (int i=l;i<=r;i++){
            if (t[i]==1) d[first[i]]=second[i];
            else {
                edge[i-l].clear();
                for (int j:update) if (d[first[j]]>=second[i]) edge[i-l].pb(first[j]);
            }
        }
        sort(all(question), [&](int a, int b){return second[a]>second[b];});
        sort(all(nochange), [&](int a, int b){return d[a]>d[b];});
        cnt=0;
        for (int qq:question){
            while (cnt<nochange.size() && d[nochange[cnt]]>=second[qq]){
                dsu.join(u[nochange[cnt]], v[nochange[cnt]]);
                cnt++;
            }
            sizz=k.size();
            for (int e:edge[qq-l]) dsu.join(u[e], v[e]);
            ans[qq]=siz[dsu.fiind(first[qq])];
            dsu.rollback(sizz);
        }
    }
    for (int i=1;i<=q;i++) if (t[i]==2) cout << ans[i] << endl;
    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'void DSU::rollback(long long int)':
bridges.cpp:38:24: 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){
      |                ~~~~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:76: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]
   76 |             while (cnt<nochange.size() && d[nochange[cnt]]>=second[qq]){
      |                    ~~~^~~~~~~~~~~~~~~~

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