Submission #723187

#	Time	Username	Problem	Language	Result	Execution time	Memory
723187		Son	Bridges (APIO19_bridges)	C++14	100 / 100	2665 ms	46768 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back

int n,m,q;
int U[100005], V[100005], W[100005];
int T[100005], X[100005], Y[100005];
int ans[100005];

int dsu[100005], sz[100005];
const int D = 1000;
bool changed[100005];
vector < int > to_join[100005],stck;

int rt( int a ){
    if ( dsu[a] == a ) return a;
    return rt(dsu[a]);
}

bool cmp_ask( int a, int b ){
    return Y[a] > Y[b];
}

bool cmp_unchanged( int a, int b ){
    return W[a] > W[b];
}

void merge( int a, int b ){
    a = rt(a);
    b = rt(b);
    if ( a == b ) return;
    if ( sz[a] > sz[b] ) swap(a,b);
    stck.pb(a);
    sz[b] += sz[a];
    dsu[a] = dsu[b];
}

void rollback( int prev_stack_size ){
    while ( stck.size() > prev_stack_size ) {
        int a = stck.back();
        stck.pop_back();
        sz[dsu[a]] -= sz[a];
        dsu[a] = a;
    } 
}

int main(){

    scanf("%d%d",&n,&m);
    for ( int i = 1; i <= m; i++ ){
        scanf("%d%d%d",&U[i],&V[i],&W[i]);
    }
    scanf("%d",&q);
    for ( int i = 1; i <= q; i++ ){
        scanf("%d%d%d",&T[i],&X[i],&Y[i]);
    }

    for ( int l = 1; l <= q; l += D){
        int r = min(q + 1, l + D );
        memset(changed,false,sizeof(changed));
        vector < int > upd,ask,unchanged;
        for ( int i = l; i < r; i++ ){
            if ( T[i] == 1 ) {
                changed[X[i]] = true;
                upd.pb(i);
            } else {
                ask.pb(i);  
            }
        }

        for ( int i = l; i < r; i++ ){
            to_join[i-l].clear();
            if ( T[i] == 1 ){
                W[X[i]] = Y[i];
                continue;
            }
            if ( T[i] == 2 ){
                for ( int j : upd ){
                    if ( W[X[j]] >= Y[i] ) to_join[i-l].pb(j);
                }
            }
        }

        for ( int i = 1; i <= m; i++ ){
            if ( !changed[i] ){
                unchanged.pb(i);
            }
        }

        sort(unchanged.begin(),unchanged.end(),cmp_unchanged);
        sort(ask.begin(),ask.end(),cmp_ask);

        for ( int i = 1; i <= n; i++ ){
            dsu[i] = i;
            sz[i] = 1;
        }

        int ptr = 0;
        for ( int i : ask ){
            while ( ptr < unchanged.size() && W[unchanged[ptr]] >= Y[i] ){
                merge(U[unchanged[ptr]], V[unchanged[ptr]]);
                ptr++;
            }
            int stack_size = (int)stck.size();
            for ( int j : to_join[i-l] ) merge(U[X[j]], V[X[j]]);
            ans[i] = sz[rt(X[i])];
            rollback(stack_size);
        }
    }


    for ( int i = 1; i <= q; i++ ) if ( T[i] == 2 ) printf("%d\n",ans[i]);
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:40:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     while ( stck.size() > prev_stack_size ) {
      |             ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:101:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             while ( ptr < unchanged.size() && W[unchanged[ptr]] >= Y[i] ){
      |                     ~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d%d%d",&U[i],&V[i],&W[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
bridges.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d%d%d",&T[i],&X[i],&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