Submission #871716

#	Time	Username	Problem	Language	Result	Execution time	Memory
871716		sleepntsheep	Bridges (APIO19_bridges)	C++17	0 / 100	1607 ms	524288 KiB

bridges

#include <iostream>
#include <cassert>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005
int B = 500;

void *PPP;
struct dsu
{
    int p[50001];
    vector<tuple<int, int, int, int>> rb;
    dsu() { memset(p, -1, sizeof p); }

    int find(int x) { return p[x] < 0 ? x : find(p[x]); }

    inline int unite(int x, int y)
    {
        if ((x = find(x)) == (y = find(y))) return 0;

        rb.emplace_back(x, y, p[x], p[y]);
        if (-p[x] > -p[y]) swap(x, y);
        //if (this == PPP) cerr << "UNITED "<<x << ' ' << y << ' ' << -p[x] << ' ' << -p[y]<<endl;
        p[y] += p[x];
        p[x] = y;
        return 1;
    }


    inline void rollback()
    {
        assert(rb.size());
        //if (this==PPP) cerr<<"ROLLBACK " <<endl;
        auto [x, y, px, py] = rb.back();
        p[x] = px, p[y] = py;
        rb.pop_back();
    }
};

vector<tuple<int, int, int>> ask[100001];
int ans[100000];

struct qt
{
    vector<tuple<int, int, int>> t[200000];

    qt()
    {
        PPP = &dsu[0];
    }

    void add(int x, int y, int eu, int ev, int ew, int v, int l, int r)
    {
        if (r < x || y < l) return;
        if (x <= l && r <= y) { t[v].emplace_back(ew, eu, ev); return; }
        int m = (l+r)/2, vr=v+(m-l+1)*2, vl=v+1;
        add(x, y, eu, ev, ew, vl, l, m), add(x, y, eu, ev, ew, vr, m+1, r);
    }

    set<tuple<int, int, int>> edges;
    struct dsu dsu[1000];
    vector<int> rec[1000];

    void push(int w, int u, int v)
    {
        for (int i = 1; i * B <= w; ++i) 
            rec[i].push_back(dsu[i].unite(u, v));
        edges.emplace(w, u, v);
    }

    void pop(int w, int u, int v)
    {
        for (int i = 1; i * B <= w; ++i) 
        {
            auto it = rec[i].back(); rec[i].pop_back();
            if (it) dsu[i].rollback();
        }
        edges.erase({w, u, v});
    }

    void dfs(int v, int l, int r)
    {
        //if (v==0) cerr<<"STARTED DFS"<<endl;
        for (auto [w, a, b] : t[v]) push(w, a, b);

        if (l == r)
        {
            for (auto [s, w, qi] : ask[l])
            {

                vector<int> rec;

                int b = w/B;
                int st = (b+1) * B - 1;
                struct dsu &d = dsu[b];

                //cerr << "4QRY " << qi << endl; for (int i = 1; i <= 4; ++i) cerr << d.p[i] << ' '; cerr << endl << endl;
                if (0&&qi == 1)
                {
                    assert(d.rb.empty());
                    cerr << "!12 " << d.p[1] << ' ' << d.p[2] << endl;
                    cerr << "b4 " << b << ' ' << -d.p[d.find(s)] << endl;
                    auto it = edges.lower_bound({st, 0, 0});
                    if (it == edges.end()) --it;
                    cerr << st << ' ' << w << endl;

                    cerr << "Edges "<<endl;
                    for (auto [w, u, v] : edges) cerr << w << ' ' << u << ' ' << v << endl;
                    cerr << "Endedges " << endl;


                    for (; it != edges.begin() && get<0>(*it) >= w; --it)
                    {
                        cerr << get<0>(*it) << ' ' << get<1>(*it) << ' ' << get<2>(*it) << endl;
                        rec.push_back(d.unite(get<1>(*it), get<2>(*it)));
                    }

                    cerr << "b5 " << b << ' ' << -d.p[d.find(s)] << endl;
                }

                auto it = prev(edges.upper_bound({st, 0, 0}));
                for (; it != edges.begin() && get<0>(*it) >= w; --it)
                    rec.push_back(d.unite(get<1>(*it), get<2>(*it)));

                ans[qi] = -d.p[d.find(s)];

                for (auto x : rec) if (x) d.rollback();

                //cerr << "5QRY " << qi << endl; for (int i = 1; i <= 4; ++i) cerr << d.p[i] << ' '; cerr << endl << endl;
            }
        }
        else
        {
            int m = (l+r)/2, vl =v+1, vr=v+(m-l+1)*2;
            dfs(vl, l, m);
            dfs(vr, m+1, r);
        }

        for (auto [w, a, b] : t[v]) pop(w, a, b);
    }
} qt;

int n, m, q, ne, nq;
tuple<int, int, int, int> el[100001];

int main()
{
    ShinLena;
    cin >> n >> m;
    {
        vector<int> C;
        for (int i = 1, u, v, w; i <= m; ++i) cin >> u >> v >> w, el[i] = {0, u, v, w}, C.push_back(w);
        cin >> q;
        vector<tuple<int, int, int>> Q(q);
        for (auto &[t, b, r] : Q) cin >> t >> b >> r, C.push_back(r);
        sort(ALL(C));
        C.erase(unique(ALL(C)), C.end());
        for (int i = 1; i <= m; ++i) get<3>(el[i]) = lower_bound(ALL(C), get<3>(el[i])) - C.begin();
        for (auto &[t, b, r] : Q) r = lower_bound(ALL(C), r) - C.begin();

        int i = 1;
        for (auto [t, b, r] : Q)
        {
            if (t == 1)
            {
                auto &[ent, u, v, w] = el[b];
                qt.add(ent, i-1, u, v, w, 0, 0, q);
                ent = i;
                w = r;
            }
            else ask[i].emplace_back(b, r, nq++);
            ++i;
        }
    }

    for (int i = 1; i <= m; ++i)
    {
        auto &[ent, u, v, w] = el[i];
        qt.add(ent, q, u, v, w, 0, 0, q);
    }


    qt.dfs(0, 0, q);

    for (int i = 0; i < nq; ++i) cout << ans[i] << '\n';


    return 0;
}

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