Submission #839312

#	Time	Username	Problem	Language	Result	Execution time	Memory
839312		Dec0Dedd	Bridges (APIO19_bridges)	C++14	100 / 100	1702 ms	10052 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3")

const int N = 1e5+10;
const int S = 2e3;

struct dsu {
    struct save {
        int v, u, szv, szu;
        save() {};
        save(int _v, int _u, int _szv, int _szu) : v(_v), u(_u), szv(_szv), szu(_szu) {}
    };

    vector<int> p, sz;
    vector<save> op;

    void init(int n) {
        p.resize(n+1), sz.resize(n+1);
        for (int i=0; i<=n; ++i) p[i]=i, sz[i]=1;
    }

    int f(int x) {
        while (p[x] != x) x=p[x];
        return x;
    }

    bool mrg(int v, int u) {
        v=f(v), u=f(u);
        if (v == u) return false;
        if (sz[u] > sz[v]) swap(v, u);
        op.push_back(save(v, u, sz[v], sz[u]));
        sz[v]+=sz[u]; p[u]=v;
        return true;
    }

    void roll() {
        if (op.empty()) return;
        save x=op.back(); op.pop_back();
        p[x.v]=x.v, p[x.u]=x.u;
        sz[x.v]=x.szv, sz[x.u]=x.szu;
    }
};

int n, m, q, a[N], b[N], w[N], tpw[N], t[N], x[N], y[N], ans[N], qs[N], chv[N], unchv[N];
bool us[N], chg[N];

void fs(int &number) {
    register int c;
    number = 0;

    c = getchar();
    for (; (c>47 && c<58); c=getchar()) number = number*10+c-48;
}

bool cmpw(int i, int j) {
    return w[i] > w[j];
}

bool cmpq(int i, int j) {
    return y[i] > y[j];
}

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

    fs(n), fs(m);
    for (int i=1; i<=m; ++i) fs(a[i]), fs(b[i]), fs(w[i]);

    fs(q);
    for (int i=1; i<=q; ++i) fs(t[i]), fs(x[i]), fs(y[i]);

    for (int l=1; l<=q; l+=S) {
        int r=min(q, l+S-1);

        int qsz=0, chsz=0, unchsz=0;
        for (int i=l; i<=r; ++i) {
            if (t[i] == 1) chg[x[i]]=true;
            else qs[qsz++]=i;
        } sort(qs, qs+qsz, cmpq);

        for (int i=1; i<=m; ++i) {
            tpw[i]=w[i];
            if (chg[i]) chv[chsz++]=i;
            else unchv[unchsz++]=i;
        } sort(unchv, unchv+unchsz, cmpw);

        dsu d; d.init(n+1);

        int p=0;
        for (int h=0; h<qsz; ++h) {
            int u=qs[h];
            int wu=y[u]; assert(t[u] == 2);

            while (p < unchsz) {
                if (wu <= w[unchv[p]]) {
                    d.mrg(a[unchv[p]], b[unchv[p]]), ++p;
                } else break;
            }

            for (int i=l; i<u; ++i) {
                if (t[i] == 2) continue;
                tpw[x[i]]=y[i];
            }

            int cnt=0;
            for (int j=0; j<chsz; ++j) {
                int g=chv[j];
                if (tpw[g] >= wu) cnt+=d.mrg(a[g], b[g]);
                tpw[g]=w[g];
            } ans[u]=d.sz[d.f(x[u])];

            while (cnt--) d.roll();
        }

        for (int i=l; i<=r; ++i) {
            if (t[i] == 2) continue;
            w[x[i]]=y[i], chg[x[i]]=false; 
        }
    }

    for (int i=1; i<=q; ++i) {
        if (t[i] == 2) printf("%d\n", ans[i]);
    }
}

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