Submission #374670

#	Time	Username	Problem	Language	Result	Execution time	Memory
374670		ijxjdjd	Bridges (APIO19_bridges)	C++14	100 / 100	2382 ms	9964 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 = 500;
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], false);
        }
        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), -K);
	fill(all(ans), -1);
	vector<int> other;
	vector<int> nother;
	other.resize(M);
	nother.resize(M);
	FR(i, M) {
        other[i] = i;
	}
	auto comp = [&](const int& lhs, const int& rhs) {
        return cur[lhs] > cur[rhs];
     };
	while (l < Q) {
        sort(all(other), comp);
        vector<int> changed;
        vector<int> respond;
        FR(i, N) {
            par[i] = i;
            rk[i] = 1;
        }
        for (int j = 0; l+j < Q && j < K; j++) {
            if (qs[l+j].t == 1) {
                if (inChng[qs[l+j].i] != l) {
                    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;
             });
        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-1 && r < Q-1) {
            if (to[r+1].first != -1) {
                cur[qs[r+1].i] = to[r+1].second;
            }
            r++;
        }
        sort(all(changed));
        assert (changed.size() == unique(all(changed))-changed.begin());
        sort(all(changed), comp);
        int a = 0;
        int b = 0;
        for (int i = 0; i < M; i++) {
            while (a < M && inChng[other[a]] == l-K) {
                a++;
            }
            if (a == M) {
                nother[i] = changed[b++];
            }
            else if (b == changed.size()) {
                nother[i] = other[a++];
            }
            else {
                if (cur[other[a]] > cur[changed[b]]) {
                    nother[i] = other[a++];
                }
                else {
                    nother[i] = changed[b++];
                }
            }
        }
        for (int i = 0; i < M; i++) {
            other[i] = nother[i];
        }
//        for (int i = 1; i < M; i++) {
//            assert (cur[other[i]] <= cur[other[i-1]]);
//        }
	}
	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()) {
      |         ~~^~~~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from bridges.cpp:1:
bridges.cpp: In function 'int main()':
bridges.cpp:174:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} [-Wsign-compare]
  174 |         assert (changed.size() == unique(all(changed))-changed.begin());
      |                 ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:185:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |             else if (b == changed.size()) {
      |                      ~~^~~~~~~~~~~~~~~~~

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