Submission #1021659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021659		ByeWorld	Bridges (APIO19_bridges)	C++14	100 / 100	2987 ms	12868 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
// #define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e5+10;
const int INF = 1e9+10;
const int LOG = 19;
const int MOD = 998244353;
const int SQRT = 450;

int n, m, q;
int e[MAXN][4], qr[MAXN][4], ans[MAXN];
int lasup[MAXN];

struct his {
    int x, y, parlama, sizlama;
};
vector <his> stac;
struct {
    int par[MAXN], siz[MAXN];
    void bd(){
        for(int i=1; i<=n; i++){
            par[i] = i; siz[i] = 1;
        }
        stac.clear();
    }
    int f(int x){ return (x==par[x] ? x : f(par[x])); }
    void mer(int x, int y){
        // cout << "mer " << x << " " << y << endl;
        x = f(x); y = f(y);
        if(x==y){
            stac.pb({x, y, par[x], siz[y]});
            return;
        }
        if(siz[x] > siz[y]) swap(x, y);
        stac.pb({x, y, par[x], siz[y]});
        par[x] = y; siz[y] += siz[x];
    }
    void rb(){
        // cout << "rollback" << endl;
        if(stac.empty()) assert(false);
        his tp = stac.back(); stac.pop_back();
        par[tp.x] = tp.parlama;
        siz[tp.y] = tp.sizlama;
    }
} DSU;
void solve(int STA){
    DSU.bd(); 
    
    vector <pair<pii,pii>> cek;
    vector <pair<pii,int>> que;
    for(int i=STA; i<min(q+1, STA+SQRT); i++){
        if(qr[i][0]==2){ // query
            que.pb({{qr[i][2], qr[i][1]}, i}); // sort by weii
            // wei, island, idx
        } else { // update
            cek.pb({{lasup[qr[i][1]], i-1}, {e[qr[i][1]][2], qr[i][1]}});
            // L - R - val - idxedge
            lasup[qr[i][1]] = i; // idx ini ke update
            e[qr[i][1]][2] = qr[i][2];
        }
    }
    for(int i=1; i<=m; i++){
        if(lasup[i] < STA) que.pb({{e[i][2], INF}, i}); // sort by wei
        // normal
        else cek.pb({{lasup[i], q}, {e[i][2], i}});
    }
    sort(que.rbegin(), que.rend());
    for(auto [XX, idx] : que){
        int node = XX.se;
        if(node!=INF){ // query ans
            // cek 
            int cnt = 0;
            for(auto [in, in2] : cek){
                if(in.se < idx || idx < in.fi || in2.fi<XX.fi) continue; 
                // harus dalem L-R, weightny >=
                cnt++;
                DSU.mer(e[ in2.se ][0], e[ in2.se ][1]);
            }
            // cout << "query: " << idx << " " << node << '\n';
            ans[idx] = DSU.siz[DSU.f(node)];
            while(cnt--){
                DSU.rb();
            }
        } else { // update edge normal
            int x = e[idx][0], y = e[idx][1];
            DSU.mer(x, y);
        }
    }
}

signed main(){
    cin >> n >> m;
    for(int i=1; i<=m; i++) cin >> e[i][0]>>e[i][1]>>e[i][2];
    cin >> q;
    for(int i=1; i<=q; i++) cin >> qr[i][0] >> qr[i][1]>>qr[i][2];
    // idx edge, wei
    for(int sta=1; sta<=q; sta+=SQRT) solve(sta);
    for(int i=1; i<=q; i++) 
        if(qr[i][0]==2) cout << ans[i] << " \n";
}

Compilation message (stderr)

bridges.cpp: In function 'void solve(int)':
bridges.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |     for(auto [XX, idx] : que){
      |              ^
bridges.cpp:84:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |             for(auto [in, in2] : cek){
      |                      ^

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