Submission #187196

#	Time	Username	Problem	Language	Result	Execution time	Memory
187196		Anai	Bridges (APIO19_bridges)	C++14	13 / 100	3075 ms	9144 KiB

bridges

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using pii = pair<int, int>;

const int N = 1e5 + 5, SQRT = 256;

struct Query {
    int idx, nod, val, ans;
};

int setval[N], far[N], val[N], cap1[N], cap2[N], bagat[N];

int tip[N], siz[N];
pii qval[N];

vector<pii> undo_stack;
int n, m, q, val_bnd;

static int uget_far(int nod) {
    return far[nod] ? uget_far(far[nod]) : nod;
}

static void ujoin(int a, int b) {
    a = uget_far(a);
    b = uget_far(b);
    if (a == b)
        return;
    if (rand() % 2)
        swap(a, b);
    far[a] = b;
    siz[b]+= siz[a];
    undo_stack.emplace_back(a, b);
}

static void undo() {
    reverse(begin(undo_stack), end(undo_stack));
    for (auto i: undo_stack) {
        far[i.x] = 0;
        siz[i.y]-= siz[i.x];
    }
    undo_stack.clear();
}

static int get_far(int nod) {
    return far[nod] ? (far[nod] = get_far(far[nod])) : nod;
}

static void join(int a, int b) {
    a = get_far(a);
    b = get_far(b);
    if (a == b)
        return;
    if (rand() % 2)
        swap(a, b);
    far[a] = b;
    siz[b]+= siz[a];
}

int main() {
#ifdef HOME
    freopen("bridges.in", "r", stdin);
    freopen("bridges.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    vector<Query> qs;
    vector<pii> back_update;

    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> cap1[i] >> cap2[i] >> setval[i];
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> tip[i];
        if (tip[i] == 1) // [1 - update, 2 - query]
            cin >> qval[i].x >> qval[i].y;
        else
            cin >> qval[i].x >> qval[i].y;
    }

    qs.reserve(SQRT);
    back_update.reserve(N);
    for (int start = 0; start < q; start+= SQRT) {
        int halt = min(q - 1, start + SQRT - 1);
        int back_ptr = 0;
        back_update.clear();
        qs.clear();

        // culege query-uri si seteaza ce nu e de bagat in back
        memset(bagat, 0x00, sizeof bagat);
        for (int i = start; i <= halt; ++i)
            if (tip[i] == 1)
                bagat[qval[i].x] = true;
            else
                qs.push_back({i, qval[i].x, qval[i].y, 0});

        // umple back_update si seteaza (back) val
        for (int i = start - 1; i >= 0; --i) if (tip[i] == 1 && !bagat[qval[i].x]) {
            bagat[qval[i].x] = true;
            back_update.emplace_back(qval[i].x, qval[i].y);
        }
        for (int i = 1; i <= m; ++i) if (!bagat[i]) {
            back_update.emplace_back(i, setval[i]);
            bagat[i] = true;
        }
        for (int i = start; i <= halt; ++i)
            if (tip[i] == 1)
                bagat[qval[i].x] = false;
        for (int i = 1; i <= m; ++i)
            val[i] = setval[i];
        for (int i = 0; i < start; ++i) if (tip[i] == 1)
            val[qval[i].x] = qval[i].y;

        sort(begin(back_update), end(back_update), [&](const pii &a, const pii &b) {
            return a.y > b.y;
        });

        // set the stage
        memset(far, 0x00, sizeof far);
        for (int i = 1; i <= n; ++i)
            siz[i] = 1;

        sort(begin(qs), end(qs), [&](const Query &a, const Query &b)  { return a.val > b.val; });
        for (auto &q: qs) {
            while (back_ptr < int(back_update.size()) && back_update[back_ptr].y >= q.val) {
                join(cap1[back_update[back_ptr].x], cap2[back_update[back_ptr].x]);
                back_ptr+= 1;
            }

            for (int i = q.idx; i >= start; --i) if (tip[i] == 1 && !bagat[qval[i].x]) {
                bagat[qval[i].x] = 2;
                if (qval[i].y < q.val)
                    continue;
                ujoin(cap1[qval[i].x], cap2[qval[i].x]);
            }

            for (int i = q.idx + 1; i <= halt; ++i) if (tip[i] == 1 && !bagat[qval[i].x]) {
                bagat[qval[i].x] = 2;
                if (val[qval[i].x] < q.val)
                    continue;
                ujoin(cap1[qval[i].x], cap2[qval[i].x]);
            }

            q.ans = siz[uget_far(q.nod)];

            // cleanup
            undo();
            for (int i = start; i <= halt; ++i) if (tip[i] == 1)
                bagat[qval[i].x] = 0;
        }


        sort(begin(qs), end(qs), [&](const Query &a, const Query &b) { return a.idx < b.idx;});
        for (auto q: qs)
            cout << q.ans << '\n';
    }

    return 0;
}

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