Submission #1082300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082300		Kuanyshh	Bridges (APIO19_bridges)	C++14	100 / 100	1641 ms	13772 KiB

bridges

#include <bits/stdc++.h>
#define x first
#define y second
#define len(x) (int)(x.size())

using namespace std;

typedef long long ll;

const int maxn = 2e5 + 7;
const int K = 1300;
const int mod = 1e9 + 7;
const int lg = 22;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int n, m, q;
int u[maxn], v[maxn], w[maxn];
int t[maxn], a[maxn], b[maxn], szb[K];
vector <int> blocks;
bool used[maxn];
int p[maxn], sz[maxn], ans[maxn];
vector <pair <int*, int>> roll_set;

int get(int v) {
    if (p[v] == v) return v;
    return get(p[v]);
}

void f(int &a, int b) {
    roll_set.push_back({&a, a});
    a = b;
}

void roll_back() {
    *(roll_set.back().first) = roll_set.back().second;
    roll_set.pop_back();
}

void unite(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    f(sz[b], sz[a] + sz[b]);
    f(p[a], b);
}

bool cmp(int i, int j) {
    return w[i] < w[j];
}

bool cmp2(int i, int j) {
    return b[i] > b[j];
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
    for (int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> w[i];
    cin >> q;
    for (int i = 1; i <= q; i++) cin >> t[i] >> a[i] >> b[i];
    for (int i = 1; i <= q; i++) {
        szb[i / K]++;
        if (i == q || i / K != (i + 1) / K) {
            blocks.push_back(i);
        }
    }
    for (auto end : blocks) {
        for (int i = 1; i <= m; i++) used[i] = 0;
        vector <int> query, changed, not_changed;
        for (int i = end - szb[end / K] + 1; i <= end; i++) {
            if (t[i] == 1) used[a[i]] = 1;
            else query.push_back(i);
        }
        for (int i = 1; i <= m; i++) {
            if (used[i]) changed.push_back(i);
            else not_changed.push_back(i);
        }
        sort(not_changed.begin(), not_changed.end(), cmp);
        sort(query.begin(), query.end(), cmp2);
        int r = len(not_changed) - 1, set_size = len(roll_set);
        for (auto x : query) {
            while (r >= 0 && w[not_changed[r]] >= b[x]) {
                unite(u[not_changed[r]], v[not_changed[r]]);
                r--;
            }
            int temp_sz = len(roll_set);
            for (int i = end - szb[end / K] + 1; i <= x; i++) {
                if (t[i] == 1) {
                    f(w[a[i]], b[i]);
                }
            }
            for (auto i : changed) {
                if (w[i] >= b[x]) {
                    unite(u[i], v[i]);
                }
            }
            ans[x] = sz[get(a[x])];
            while (len(roll_set) > temp_sz) roll_back();
        }
        while (len(roll_set) > set_size) roll_back();
        for (int i = end - szb[end / K] + 1; i <= end; i++) {
            if (t[i] == 1) {
                w[a[i]] = b[i];
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        if (t[i] == 2) {
            cout << ans[i] << '\n';
        }
    }
}

const bool cases = 0;

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

    int test = 1, cnt = 0;
    if (cases) cin >> test;
    while (test--) {
//        cout << "Case " << ++cnt << ":\n";
        solve();
    }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:122:19: warning: unused variable 'cnt' [-Wunused-variable]
  122 |     int test = 1, cnt = 0;
      |                   ^~~

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