Submission #187316

#	Time	Username	Problem	Language	Result	Execution time	Memory
187316		Anai	Bridges (APIO19_bridges)	C++14	30 / 100	3048 ms	21988 KiB

bridges

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

struct ParseIn {
    static const int BMAX = 1 << 20;

    char buff[BMAX];
    int bp;
    FILE *fi;

    ParseIn(string str) {
        fi = fopen(str.c_str(), "r");
	bp = BMAX; }
    ParseIn() {
	fi = stdin;
        bp = BMAX; }

    char nextch() {
	if (bp == BMAX) {
            fread(buff, 1, BMAX, fi);
    	    bp = 0;
        }
	return buff[ bp++ ]; }

    ParseIn &operator >> (int &num) {
        char ch;
        num = 0;
        do {
            ch = nextch();
        }
        while (ch < '0' || '9' < ch);
        while ('0' <= ch && ch <= '9') {
            num = num * 10 + (ch - '0');
            ch = nextch();
        }
        return *this;
    }
} fi;


using pii = pair<int, int>;

const int N = 5e4 + 5, M = 1e5 + 5, V = 3e5 + 5;

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

vector<pii> bucket[V];
int setval[M], far[N], ufar[N], usiz[N], val[M], cap1[M], cap2[M], bagat[M];

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

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

static void mare_normalizare() {
    map<int, int> mp;
    for (int i = 1; i <= m; ++i)
        mp[setval[i]] = 0;
    for (int i = 0; i < q; ++i)
        mp[qval[i].y] = 0;
    for (auto &i: mp)
        i.y = val_bnd++;
    for (int i = 1; i <= m; ++i)
        setval[i] = mp[setval[i]];
    for (int i = 0; i < q; ++i)
        qval[i].y = mp[qval[i].y];
}

static void bsort(vector<pii> &upd) {
    int bnd = 0;
    for (auto i: upd) {
        bucket[i.y].push_back(i);
        bnd = max(bnd, i.y);
    }
    upd.clear();
    for (int i = bnd; i >= 0; --i) {
        for (auto j: bucket[i])
            upd.push_back(j);
        bucket[i].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];
}

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

static void ujoin(int a, int b) {
    a = uget_far(get_far(a));
    b = uget_far(get_far(b));

    if (usiz[a] == 0)
        usiz[a] = siz[a];
    if (usiz[b] == 0)
        usiz[b] = siz[b];

    undo_stack.push_back(a);
    undo_stack.push_back(b);

    if (a == b)
        return;
    if (rand() % 2)
        swap(a, b);

    ufar[a] = b;
    usiz[b]+= usiz[a];
}

static void undo() {
    for (auto i: undo_stack) {
        ufar[i] = 0;
        usiz[i] = 0;
    }
    undo_stack.clear();
}

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;

    fi >> n >> m;
    for (int i = 1; i <= m; ++i)
        fi >> cap1[i] >> cap2[i] >> setval[i];
    fi >> q;
    for (int i = 0; i < q; ++i)
        fi >> tip[i] >> qval[i].x >> qval[i].y;

    mare_normalizare();
    qs.reserve(M);
    back_update.reserve(M);
    undo_stack.reserve(M);
    int pas, halt;
    int sum = 0;
    for (int start = 0; start < q; start = halt + 1) {
        pas = sqrt(m + sum) * 3 + 5;
        halt = min(q - 1, start + pas);

        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;
                sum+= 1; }
            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;

        bsort(back_update);
//        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;
            }

            if (siz[get_far(q.nod)] != n) {
                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 = max(siz[get_far(q.nod)], usiz[uget_far(get_far(q.nod))]);

                // cleanup
                undo();
                for (int i = start; i <= halt; ++i) if (tip[i] == 1)
                    bagat[qval[i].x] = 0;
            }
            else
                q.ans = max(siz[get_far(q.nod)], usiz[uget_far(get_far(q.nod))]);
        }

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

    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'char ParseIn::nextch()':
bridges.cpp:23:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buff, 1, BMAX, fi);
             ~~~~~^~~~~~~~~~~~~~~~~~~

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