Submission #1281369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281369		luvna	Bridges (APIO19_bridges)	C++20	100 / 100	1697 ms	109280 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) << "]"
#define vi vector<int>

using namespace std;
bool START_ALLOC;

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_64 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 MAX = 2e5 + 15;
const int block_sz = 900;

int n, m, q;
int eu[MAX], ev[MAX], ew[MAX];
int type[MAX], qU[MAX], qD[MAX];
bool use[MAX];

struct DSU{
    int n;
    vector<int> lab;
    stack<pair<int&, int>> stk;

    DSU(int n) : n(n), lab(n + 15, -1) {}

    int asc(int u){
        return lab[u] < 0 ? u : asc(lab[u]);
    }

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

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

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

    int siz(int u){
        u = asc(u);
        return -lab[u];
    }
};

vector<int> sideEdges[MAX];
int ans[MAX];

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] >> qU[i] >> qD[i]; --type[i];
    }

    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> query;
        for(int i = l; i <= r; i++){
            if(!type[i]) use[qU[i]] = true;
            else query.push_back(i);
        }

        //split group edges
        vector<int> touch, untouch;
        for(int i = 1; i <= m; i++){
            if(use[i]) touch.push_back(i);
            else untouch.push_back(i);
            use[i] = false;
        }

        for(int i = l; i <= r; i++){
            if(!type[i]) ew[qU[i]] = qD[i];
            else{
                for(int id : touch){
                    //edges that change before i and is bigger than i
                    if(ew[id] >= qD[i]){
                        sideEdges[i].push_back(id);
                    }
                }
            }
        }

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

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

        int big_snap = dsu.snap();

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

            int small_snap = dsu.snap();

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

            ans[query[i]] = dsu.siz(qU[query[i]]);

            dsu.rollback(small_snap);
        }

        dsu.rollback(big_snap);
    }

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

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

    #define task "task"

    cerr << "[Static Memory : " << fixed << setprecision(2) << (((&END_ALLOC) - (&START_ALLOC)) / (1024.0 * 1024.0)) << "mb]\n";
    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:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         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