제출 #511227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
511227		blue	다리 (APIO19_bridges)	C++17	44 / 100	3094 ms	11760 KiB

bridges

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;

const int rt = 1000;

int n, m;
vi u, v, w;

int q;
vi t;
vi b, r;
vi s, c;

struct change
{
    int u;
    int op;
    int typ;
};

struct disjoint_set
{
    vi parent;
    vi subtree;

    vector<change> changes; //node, type(0/1)

    disjoint_set()
    {
        parent = vi(1+n);
        subtree = vi(1+n, 1);
        for(int i = 0; i <= n; i++) parent[i] = i;
    }

    int root(int u)
    {
        if(parent[u] == u) return u;
        else if(parent[parent[u]] == parent[u]) return parent[u];
        else
        {
            changes.push_back({u, parent[u], 0});
            parent[u] = root(parent[u]);
            return parent[u];
        }
    }

    void join(int u, int v)
    {
        changes.push_back({-1, -1, -1});
        u = root(u);
        v = root(v);
        if(u == v)
        {
            // cerr << "change rejected\n";
            changes.push_back({0, 0, 0});
        }
        else
        {
            if(subtree[u] < subtree[v]) swap(u, v);
            changes.push_back({v, parent[v], 1});
            parent[v] = u;
            subtree[u] += subtree[v];
            // changes.push_back(v);
            // cerr << "making " << u << " parent of " << v << '\n';
        }
    }

    void rollback()
    {
        while(1)
        {
            int u = changes.back().u;
            int op = changes.back().op;
            int typ = changes.back().typ;
            changes.pop_back();

            if(u == -1) return;

            if(typ == 1)
            {
                subtree[parent[u]] -= subtree[u];
                parent[u] = op;
            }
            else
            {
                parent[u] = op;
            }
        }

    }

    int reach(int u)
    {
        return subtree[root(u)];
    }
};


int wt(int d)
{
    if(d > 0)
    {
        return w[d];
    }
    else
    {
        return c[-d];
    }
}


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

    cin >> n >> m;

    u = v = w = vi(1+m);
    for(int e = 1; e <= m; e++) cin >> u[e] >> v[e] >> w[e];

    cin >> q;
    t = b = r = s = c = vi(q);
    for(int j = 0; j < q; j++)
    {
        cin >> t[j];
        if(t[j] == 1) cin >> b[j] >> r[j];
        else cin >> s[j] >> c[j];
    }


    vi ans(q, -1);

    vi temp_edge_found(1+m, 0);


    for(int bl = 0; bl <= (q-1)/rt; bl++)
    {
        int y = rt*bl;
        int z = min(rt*(bl+1)-1, q-1);

        // cerr << "current block = " << y << ' ' << z << '\n';

        vi mod(1+m);
        for(int j = y; j <= z; j++)
            if(t[j] == 1)
                mod[b[j]] = 1;

        vi ops;
        for(int e = 1; e <= m; e++)
            if(!mod[e])
                ops.push_back(e);

        for(int j = y; j <= z; j++)
            if(t[j] == 2)
                ops.push_back(-j);

        sort(ops.begin(), ops.end(), [] (int d, int f)
        {
            int wd = wt(d), wf = wt(f);
            if(wd != wf) return wd > wf;
            else return d > f;
        });

        disjoint_set dsu;


        for(int o: ops)
        {
            // cerr << "\n\n\n";
            if(o > 0)
            {
                dsu.join(u[o], v[o]);
                // cerr << "general join: " << o << '\n';
            }
            else
            {
                int qr = -o;
                int curr_ct = 0;

                // cerr << "answering query : " << qr << '\n';

                for(int l = qr-1; l >= y; l--)
                {
                    if(t[l] == 2) continue;
                    if(temp_edge_found[b[l]]) continue;

                    temp_edge_found[b[l]] = 1;

                    if(r[l] >= c[qr])
                    {
                    // cerr << "query specific join 1: " << b[l] << '\n';
                        dsu.join(u[b[l]], v[b[l]]);
                        curr_ct++;
                    }
                }

                for(int l = qr+1; l <= z; l++)
                {
                    // cerr << "l = " << l << '\n';
                    if(t[l] == 2) continue;
                    if(temp_edge_found[b[l]]) continue;
                    // cerr << "success!\n";

                    temp_edge_found[b[l]] = 1;

                    // cerr << b[l] << " > " << w[b[l]] << ' ' << c[qr] << '\n';
                    if(w[b[l]] >= c[qr])
                    {
                    // cerr << "query specific join 2: " << b[l] << '\n';
                        dsu.join(u[b[l]], v[b[l]]);
                        curr_ct++;
                    }
                }

                ans[qr] = dsu.reach(s[qr]);


                for(int ct = 0; ct < curr_ct; ct++)
                {

                    // cerr << "rollback\n";
                        dsu.rollback();
                }

                for(int l = y; l <= z; l++)
                {
                    if(t[l] == 1)
                    {
                        temp_edge_found[b[l]] = 0;
                    }
                }


            }
        }

        for(int l = y; l <= z; l++)
        {
            if(t[l] == 1)
            {
                w[b[l]] = r[l];
            }
        }


    }

    for(int j = 0; j < q; j++)
        if(t[j] == 2)
            cout << ans[j] << '\n';
}

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