Submission #374646

#	Time	Username	Problem	Language	Result	Execution time	Memory
374646		ijxjdjd	Bridges (APIO19_bridges)	C++14	14 / 100	3072 ms	10132 KiB

bridges

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int K = 10000;
const int MAXM = 100000;
const int MAXN = 50000;
int E[MAXM][3];


int par[MAXN];
int rk[MAXN];
int cur[MAXM];

int find(int x, bool alpha = true) {
    if (par[x] == x) {
        return x;
    }
    else {
        if (!alpha) {
            return find(par[x]);
        }
        else {
            return (par[x] = find(par[x]));
        }
    }
}
void merge(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px != py) {
        if (rk[py] > rk[px]) {
            swap(px, py);
        }
        par[py] = px;
        rk[px] += rk[py];
    }
}
int dfMerge(vector<int>& arr, int i, int low, int a) {
    if (i == arr.size()) {
        return rk[find(a, false)];
    }
    else {
        if (cur[arr[i]] >= low) {
            int px = find(E[arr[i]][0], false);
            int py = find(E[arr[i]][1], false);
            if (px != py) {
                if (rk[px] < rk[py]) {
                    swap(px, py);
                }
                par[py] = px;
                rk[px] += rk[py];
                int ans = dfMerge(arr, i+1, low, a);
                par[py] = py;
                rk[px] -= rk[py];
                return ans;
            }
            else {
                return dfMerge(arr, i+1, low, a);
            }
        }
        else {
            return dfMerge(arr, i+1, low, a);
        }
    }
}
int inChng[MAXM];
pair<int, int> to[MAXM];

struct Query {
    int t, i, j;
};
Query qs[MAXM];
int ans[MAXM];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
        cin >> E[i][0] >> E[i][1] >> E[i][2];
        E[i][0]--;
        E[i][1]--;
        cur[i] = E[i][2];
	}
	int Q;
	cin >> Q;
	FR(i, Q) {
        cin >> qs[i].t >> qs[i].i >> qs[i].j;
        qs[i].i--;
        if (qs[i].t == 1) {
            to[i].first = cur[qs[i].i];
            to[i].second = qs[i].j;
            cur[qs[i].i] = qs[i].j;
        }
        else {
            to[i].first = -1;
        }
	}
	FR(i, M) {
        cur[i] = E[i][2];
	}

	int l = 0;
	int r = -1;
	fill(all(inChng), -1);
	fill(all(ans), -1);
	while (l < Q) {
        vector<int> changed;
        vector<int> respond;
        vector<int> other;
        FR(i, N) {
            par[i] = i;
            rk[i] = 1;
        }
        FR(iter, M) {
            other.push_back(iter);
        }
        for (int j = 0; l+j < Q && j < K; j++) {
            if (qs[l+j].t == 1) {
                changed.push_back(qs[l+j].i);
                inChng[qs[l+j].i] = l;
            }
            else {
                respond.push_back(l+j);
            }
        }
        sort(all(respond), [] (const int& lhs, const int& rhs) {
                return qs[lhs].j > qs[rhs].j;
             });
        sort(all(other), [](const int& lhs, const int& rhs) {
                return cur[lhs] > cur[rhs];
             });
        int u = 0;
        for (int next : respond) {
            while (r < next) {
                if (to[r+1].first != -1) {
                    cur[qs[r+1].i] = to[r+1].second;
                }
                r++;
            }
            while (r > next) {
                if (to[r].first != -1) {
                    cur[qs[r].i] = to[r].first;
                }
                r--;
            }
            while (u < M && (inChng[other[u]] == l || cur[other[u]] >= qs[next].j)) {
                if (inChng[other[u]] != l) {
                    merge(E[other[u]][0], E[other[u]][1]);
                }
                u++;
            }
            ans[r] = dfMerge(changed, 0, qs[next].j, qs[next].i);
        }
        l += K;
        while (r < l && r < Q-1) {
            if (to[r+1].first != -1) {
                cur[qs[r+1].i] = to[r+1].second;
            }
            r++;
        }
	}
	for (int i = 0; i < Q; i++) {
        if (ans[i] != -1) {
            cout << ans[i] << '\n';
        }
	}
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int dfMerge(std::vector<int>&, int, int, int)':
bridges.cpp:44:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     if (i == arr.size()) {
      |         ~~^~~~~~~~~~~~~

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