Submission #577045

#	Time	Username	Problem	Language	Result	Execution time	Memory
577045		training4usaco	Bridges (APIO19_bridges)	C++11	30 / 100	3057 ms	239948 KiB

bridges

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

#define int long long

#define MAXN 50005
#define MAXM 100005
#define BLOCK 320

int n, m, q;

int u[MAXM], v[MAXM], w[MAXM];
int type[MAXM], x[MAXM], y[MAXM];

int par[MAXN], sizes[MAXN];
stack<int> history;

int ans[MAXM];
vector<int> addon[MAXM];

int getRoot(int x){
    if(par[x] == x) {
        return x;
    }
    return getRoot(par[x]);
}
 
void merge(int x, int y){
    x = getRoot(x); 
    y = getRoot(y);

    if(x == y) {
        return;
    }

    if(sizes[x] > sizes[y]) {
        swap(x, y);
    }
    history.push(x);
    par[x] = y;
    sizes[y] += sizes[x];

    return;
}
 
void rollback(int snapshot){
    while((int)history.size() > snapshot){
        int x = history.top(); 
        history.pop();

        sizes[par[x]] -= sizes[x];
        par[x] = x;
    }
    return;
}

bool cmp1(const int &a, const int &b) {
    return w[a] > w[b];
}

bool cmp2(const int &a, const int &b) {
    return y[a] > y[b];
}
 
signed main(){
    ios::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0);
    cin >> n >> m;

    for(int i = 1; i <= m; ++i) {
        cin >> u[i] >> v[i] >> w[i];
    }

    cin >> q;
    for(int i = 1; i <= q; ++i) {
        cin >> type[i] >> x[i] >> y[i];
    }

    for(int l = 1; l <= q; l += BLOCK) {
        vector<bool> changed(m + 1, false);

        for(int i = 1; i <= n; ++i) {
            par[i] = i;
            sizes[i] = 1;
        }

        int r = min(l + BLOCK - 1, q);
 
        vector<int> update; // index of queries that are changes
        vector<int> queries;  // actual queries

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

        vector<int> unchanged;
        for(int i = 1; i <= m; ++i) {
            if(!changed[i]) {
                unchanged.push_back(i);
            }
        }

        for(int i = l; i <= r; ++i) {
            if(type[i] == 1) {
                w[x[i]] = y[i];
            }
            else {
                for(auto qidx : update) {   // this edge now works :yayy:
                    if(w[x[qidx]] >= y[i]) {
                        addon[i].push_back(x[qidx]); 
                    }
                }
            }
        }

        // just do normally (naively) ignoring if there are updates
        // add in any extra nodes that can work because of previous
        // updates (changes)

        sort(unchanged.begin(), unchanged.end(), cmp1);
        sort(queries.begin(), queries.end(), cmp2);

        int idx = 0;
        for(auto query : queries) {
            while(idx < unchanged.size() && w[unchanged[idx]] >= y[query]) {    // normal w/o update algo
                merge(u[unchanged[idx]], v[unchanged[idx]]);
                ++idx;
            }

            int snapshot = history.size();
            for(auto extra : addon[query]) {
                merge(u[extra], v[extra]);
            }


            ans[query] = sizes[getRoot(x[query])];

            rollback(snapshot);
        }
    }

    for(int i = 1; i <= q; ++i){
        if(type[i] == 2) {
            cout << ans[i] << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:136:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             while(idx < unchanged.size() && w[unchanged[idx]] >= y[query]) {    // normal w/o update algo
      |                   ~~~~^~~~~~~~~~~~~~~~~~

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