Submission #369408

#	Time	Username	Problem	Language	Result	Execution time	Memory
369408		cpp219	Bridges (APIO19_bridges)	C++14	100 / 100	2979 ms	10028 KiB

bridges

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll mod = 1e9 + 7;
const ll B = 1000;
struct Edge{
    ll u,v,w;
};
Edge a[N];

struct Query{
    ll type,x,y;
};
Query q[N];
ll n,m,ans[N],lab[N],Q,prv[N];
vector<ll> change,unchange;
bool Is_change[N];
stack<LL> st;
bool lf(ll x,ll y){
    return a[x].w > a[y].w;
}

ll Find(ll u){
    if (lab[u] < 0) return u;
    return Find(lab[u]);
}

void Union(ll P,ll Q){
    ll r = Find(P),s = Find(Q);
    if (r == s) return;
    if (lab[r] > lab[s]) swap(r,s);
    st.push({r,lab[r]}); st.push({s,lab[s]});
    lab[r] += lab[s]; lab[s] = r;
}

void rollback(ll now){
    while(st.size() > now){
        lab[st.top().fs] = st.top().sc;
        st.pop();
    }
}
vector<ll> type2;

bool cmp(ll a,ll b){
    return q[a].y > q[b].y;
}

bool cmp1(ll a,ll b){
    return q[a].y < q[b].y;
}

void oper(ll L,ll R){
    memset(Is_change,0,sizeof(Is_change)); memset(lab,-1,sizeof(lab));
    change.clear(); unchange.clear(); type2.clear();
    vector<ll> to_join[1003];
    while(st.size()) st.pop();
    for (ll i = L;i <= R;i++){
        if (q[i].type == 1) Is_change[q[i].x] = 1,change.emplace_back(i);
        else type2.emplace_back(i);
    }
    for (ll i = 1;i <= m;i++) if (!Is_change[i]) unchange.emplace_back(i);
    for (ll i = L;i <= R;i++){
        if (q[i].type == 1) a[q[i].x].w = q[i].y;
        else{
            to_join[i - L].clear();
            for (auto j : change) if (a[q[j].x].w >= q[i].y) to_join[i - L].emplace_back(q[j].x);
        }
    }
    sort(unchange.begin(),unchange.end(),lf); sort(type2.begin(),type2.end(),cmp);
    ll cur = 0;
    for (auto i : type2){
        while(cur < unchange.size() && a[unchange[cur]].w >= q[i].y){
            Edge p = a[unchange[cur]]; Union(p.u,p.v);
            cur++;
        }
        ll prv = st.size();
        for (auto j : to_join[i - L]) Union(a[j].u,a[j].v);
        ans[i] = -lab[Find(q[i].x)];
        rollback(prv);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n>>m;
    for (ll i = 1;i <= m;i++) cin>>a[i].u>>a[i].v>>a[i].w;
    cin>>Q;
    for (ll i = 1;i <= Q;i++) cin>>q[i].type>>q[i].x>>q[i].y;
    for (ll i = 1;i <= Q;i += B) oper(i,min(Q,i + B - 1));
    for (ll i = 1;i <= Q;i++) if (ans[i]) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

bridges.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
bridges.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
bridges.cpp: In function 'void rollback(int)':
bridges.cpp:46:21: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |     while(st.size() > now){
      |           ~~~~~~~~~~^~~~~
bridges.cpp: In function 'void oper(int, int)':
bridges.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         while(cur < unchange.size() && a[unchange[cur]].w >= q[i].y){
      |               ~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   97 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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