Submission #1066899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066899		doducanh	Bridges (APIO19_bridges)	C++14	100 / 100	1575 ms	32592 KiB

bridges

///breaker
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
const int maxm=1e5+7;
const int maxn=5e4+7;
const int B=1000;
struct edges
{
    int u,v,w;
};
struct query
{
    int t,x,y;
};
edges e[maxm];
query q[maxm];
int ans[maxm];
int n,m,qu;
vector<int>to_add[1005];
int r[maxm];
int sz[maxm];
void reset()
{
    for(int i=1;i<=n;i++){
        r[i]=i;
        sz[i]=1;
    }
}
inline int Find(int a) {
	while (r[a] != a) a = r[a];
	return a;
}
stack<int>st;
void Union(int u,int v)
{
    u=Find(u);
    v=Find(v);
    if(u==v)return;
    if(sz[u]>sz[v])swap(u,v);
    st.push(u);
    sz[v]+=sz[u];
    r[u]=r[v];

}
void roll_back(int x)
{
    while(st.size()>x){
        int u=st.top();
//        cout<<u<<" "<<sz[u]<<"\n";
        st.pop();
        sz[r[u]]-=sz[u];
        r[u]=u;
    }
}
void sol(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    cin>>qu;
    for(int i=1;i<=qu;i++){
        cin>>q[i].t>>q[i].x>>q[i].y;
    }
    for(int l=1;l<=qu;l+=B){
        int r=min(l+B-1,qu);
        reset();
        vector<int>up,add;
        vector<bool>is_up(m+1,0);
        for(int i=l;i<=r;i++){
            if(q[i].t==1){
                is_up[q[i].x]=1;
                up.push_back(i);
            }
            else{
                add.push_back(i);
            }
        }
        for(int i=l;i<=r;i++){
            if(q[i].t==1){
                e[q[i].x].w=q[i].y;
            }
            else{
                to_add[i-l].clear();
                for(int j:up){
                    if(e[q[j].x].w>=q[i].y){
                        to_add[i-l].push_back(q[j].x);
                    }
                }
            }
        }
        vector<int>unchanged;
        for(int i=1;i<=m;i++){
            if(!is_up[i]){
                unchanged.push_back(i);
            }
        }
        sort(unchanged.begin(),unchanged.end(),[&](int a,int b){return e[a].w>e[b].w;});
        sort(add.begin(),add.end(),[&](int a,int b){return q[a].y>q[b].y;});
        int lo=0;
        for(int i:add){
            while(lo<unchanged.size()&&e[unchanged[lo]].w>=q[i].y){
                Union(e[unchanged[lo]].u,e[unchanged[lo]].v);
                lo++;
            }
//            cout<<17<<" "<<sz[Find(7)]<<"\n";
            int pre_size=st.size();
            for(int j:to_add[i-l]){
//                cout<<j<<" "<<e[j].u<<" "<<e[j].v<<" ";
                Union(e[j].u,e[j].v);
//                cout<<sz[Find(e[j].u)]<<"\n";
            }
            ans[i]=sz[Find(q[i].x)];
//            cout<<i<<" "<<ans[i]<<"\n";
            roll_back(pre_size);
////            cout<<17<<" "<<sz[Find(7)]<<"\n";
        }

    }
    for(int i=1;i<=qu;i++){
        if(q[i].t==2){
            cout<<ans[i]<<"\n";
        }
    }
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

bridges.cpp: In function 'void roll_back(int)':
bridges.cpp:55:20: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     while(st.size()>x){
      |           ~~~~~~~~~^~
bridges.cpp: In function 'void sol()':
bridges.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |             while(lo<unchanged.size()&&e[unchanged[lo]].w>=q[i].y){
      |                   ~~^~~~~~~~~~~~~~~~~
bridges.cpp: At global scope:
bridges.cpp:133:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  133 | main()
      | ^~~~

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