Submission #1045954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045954		dead0ne	Bridges (APIO19_bridges)	C++17	0 / 100	873 ms	13540 KiB

bridges

#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define int long long
#define ii pair<long long,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define inf 1e15
#define MOD 1000000007
#define MX 50005
using namespace std;


const int B=1000;
int sz[MX], cmp[MX];
stack<int> hist;
int find(int x){
    if(cmp[x]==x) return x;
    return find(cmp[x]);
}
void unite(int x, int y){
    x=find(x), y=find(y);
    if(x==y)return;
    if(sz[x]>sz[y]) swap(x,y);
    hist.push(x);
    sz[y]+=sz[x];
    cmp[x]=y;
}
void rollback(int x){
    while(hist.size()>x){
        int f=hist.top();
        hist.pop();
        sz[cmp[f]]-=sz[f];
        cmp[f]=f;
    }
}

int u[2*MX], v[2*MX], w[2*MX];
int ty[2*MX], x[2*MX], y[2*MX];
int ans[2*MX];
bool changed[2*MX];
vi to_join[B];

void solve(){
    int n,m,q; 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 >> ty[i] >> x[i] >> y[i];

    int l,r;
    for(l=1; l<=q; l+=B){
        r = min(q, l+B-1);
        fill(changed+1, changed+n+1, false);
        fill(sz+1, sz+n+1, 1);
        for(int i=1; i<=n; i++) cmp[i]=i;
        vi ask, upd, unchanged;

        for(int i=l; i<=r; i++){
            if(ty[i]==1){
                changed[x[i]]=true;
                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(ty[i]==1) w[x[i]]=y[i];
            else{
                to_join[i-l].clear();
                for(auto j:upd) if(w[x[j]]>=y[i]) to_join[i-l].pb(j);
            }
        }

        sort(all(ask), [&](int a, int b){ return y[a]>y[b]; });
        sort(all(unchanged), [&](int a, int b){ return w[x[a]]>w[x[b]]; });
        int ptr=0;
        for(auto i:ask){
            while(ptr<unchanged.size() && w[unchanged[ptr]]>=y[i]){
                unite(u[unchanged[ptr]], v[unchanged[ptr]]);
                ptr++;
            }
            int cur = hist.size();
            for(auto j:to_join[i-l]){
                unite(u[x[j]], v[x[j]]);
            }
            ans[i] = sz[find(x[i])];
            rollback(cur);
        }
    }
    for(int i=1; i<=q; i++) if(ty[i]==2) cout << ans[i] << endl;
}
 
 
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    #ifdef Local
    freopen("in","r",stdin);
    freopen("out","w",stdout);
    #endif
 
    /*freopen("nondec.in","r",stdin);
    freopen("nondec.out","w",stdout);*/
 
    int t=1;
    //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(long long int)':
bridges.cpp:36:22: 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]
   36 |     while(hist.size()>x){
      |           ~~~~~~~~~~~^~
bridges.cpp: In function 'void solve()':
bridges.cpp:85:22: 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]
   85 |             while(ptr<unchanged.size() && w[unchanged[ptr]]>=y[i]){
      |                   ~~~^~~~~~~~~~~~~~~~~

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