Submission #1125980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125980		luvna	Bridges (APIO19_bridges)	C++20	100 / 100	1828 ms	118508 KiB

bridges

#include<bits/stdc++.h>

#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}

typedef long long ll;
typedef long double ld;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

const int N = 5e5 + 15;

int n, m, q;
int eu[N], ev[N], ew[N];
int type[N], queryU[N], queryD[N];

struct DSU{
    int n;
    vector<int> par, siz;
    stack<pair<int &, int>> st;

    DSU() {}

    DSU(int n) : n(n), par(n + 15, 0), siz(n + 15, 0) {
        for(int i = 1; i <= n; i++) par[i] = i, siz[i] = 1;
    }

    int asc(int u){
        return par[u] == u ? u : asc(par[u]);
    }

    void join(int u, int v){
        u = asc(u), v = asc(v);
        if(u == v) return;
        if(siz[v] > siz[u]) swap(u,v);
        st.push({par[v], par[v]});
        st.push({siz[u], siz[u]});
        par[v] = u;
        siz[u] += siz[v];
    }

    int snap() {return sz(st);}

    void rollback(int snapshot){
        assert(snap() >= snapshot);
        while(snap() > snapshot){
            st.top().fi = st.top().se;
            st.pop();
        }
    }
};

namespace subtask1{
    bool check(void){
        return n <= 1000 && m <= 1000 && q <= 10000;
    }

    void main(){
        DSU dsu(n);

        for(int i = 0; i < q; i++){
            if(type[i] == 1){
                ew[queryU[i]] = queryD[i];

            }
            else{
                int snapshot = dsu.snap();
                for(int j = 1; j <= m; j++){
                    if(ew[j] >= queryD[i]) dsu.join(eu[j], ev[j]);
                }
                cout << dsu.siz[dsu.asc(queryU[i])] << endl;
                dsu.rollback(snapshot);
            }
        }
    }
}

namespace subtask4{
    bool check(void){
        for(int i = 0; i < q; i++) if(type[i] == 1) return false;
        return true;
    }

    int ans[N];

    void main(){
        vector<int> queryID, edgesID;

        DSU dsu(n);

        for(int i = 0; i < q; i++) queryID.push_back(i);

        sort(all(queryID), [&](int i, int j){
            return queryD[i] > queryD[j];
        });

        for(int i = 1; i <= m; i++) edgesID.push_back(i);

        sort(all(edgesID), [&](int i, int j){
            return ew[i] > ew[j];
        });

        for(int i = 0, j = 0; i < sz(queryID); i++){
            while(j < sz(edgesID) && ew[edgesID[j]] >= queryD[queryID[i]]){
                dsu.join(eu[edgesID[j]], ev[edgesID[j]]);
                j++;
            }
            ans[queryID[i]] = dsu.siz[dsu.asc(queryU[queryID[i]])];
        }

        for(int i = 0; i < q; i++) cout << ans[i] << endl;
    }
}

namespace subtask6{
    const int block_sz = 800;

    int ans[N];
    bool changed[N];
    vector<int> sideEdge[N];

    void main(){
        DSU dsu(n);

        for(int block = 0; block <= q / block_sz; block++){
            int l = block*block_sz;
            int r = min(q-1, (block+1)*block_sz-1);

            vector<int> queryBlock;

            for(int i = l; i <= r; i++){
                if(type[i] == 1) changed[queryU[i]] = true;
                else queryBlock.push_back(i);
            }

            vector<int> dynamic_edge, untouch_edge;

            for(int i = 1; i <= m; i++){
                if(changed[i]) dynamic_edge.push_back(i);
                else untouch_edge.push_back(i);
                changed[i] = false;
            }

            //update query in this block, add edges that might be useful for ask-queries

            for(int i = l; i <= r; i++){
                if(type[i] == 1) ew[queryU[i]] = queryD[i];
                else{
                    for(int id : dynamic_edge){
                        if(ew[id] >= queryD[i]){
                            sideEdge[i].push_back(id);
                        }
                    }
                }
            }

            //offline like subtask 4 + side edge

            sort(all(queryBlock), [&](int i, int j){
                return queryD[i] > queryD[j];
            });

            sort(all(untouch_edge), [&](int i, int j){
                return ew[i] > ew[j];
            });

            int big_snap = dsu.snap();

            for(int i = 0, j = 0; i < sz(queryBlock); i++){
                while(j < sz(untouch_edge) && ew[untouch_edge[j]] >= queryD[queryBlock[i]]){
                    int id = untouch_edge[j];
                    dsu.join(eu[id], ev[id]);
                    j++;
                }

                int small_snap = dsu.snap();

                for(int id : sideEdge[queryBlock[i]]){
                    dsu.join(eu[id], ev[id]);
                }

                ans[queryBlock[i]] = dsu.siz[dsu.asc(queryU[queryBlock[i]])];

                dsu.rollback(small_snap);
            }

            dsu.rollback(big_snap);
        }

        for(int i = 0; i < q; i++) if(type[i] == 2) cout << ans[i]  << endl;
    }
}

void solve(){
    cin >> n >> m;

    for(int i = 1; i <= m; i++) cin >> eu[i] >> ev[i] >> ew[i];

    cin >> q;

    for(int i = 0; i < q; i++) cin >> type[i] >> queryU[i] >> queryD[i];

    /*if(subtask1::check()) subtask1::main();
    else if(subtask4::check()) subtask4::main();
    else*/ subtask6::main();
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:229:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  229 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:230:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  230 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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