Submission #216442

#	Time	Username	Problem	Language	Result	Execution time	Memory
216442		usachevd0	Bridges (APIO19_bridges)	C++14	43 / 100	1135 ms	58100 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

void debug_out()
{
    cerr << endl;
}

template<typename T1, typename... T2> void debug_out(T1 A, T2... B)
{
    cerr << ' ' << A;
    debug_out(B...);
}

#ifdef DEBUG
    #define time(...) 42
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 42
#endif

template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }

mt19937 rng(time(0));
const int INF32 = 1e9 + 1337 + 228 + 1488;
const int maxV = 50004;
const int maxE = 100005;
const int maxQ = 100005;
int eV[maxE], eU[maxE], eF[maxE];
int qT[maxQ], qI[maxE], qF[maxE];
vector<pii> G[maxV];

namespace treap
{
    struct Node
    {
        int x, y, sz;
        Node *l, *r;

        Node() {}
        Node(int _x): x(_x), y(rng()), sz(1), l(0), r(0) {}
    };

    int sz(Node *&t)
    {
        return t ? t->sz : 0;
    }

    void upd(Node *&t)
    {
        if (t)
        {
            t->sz = sz(t->l) + 1 + sz(t->r);
        }
    }

    Node* merge(Node *a, Node *b)
    {
        if (!a) return b;
        if (!b) return a;
        if (a->y > b->y)
        {
            a->r = merge(a->r, b);
            upd(a);
            return a;
        }
        else
        {
            b->l = merge(a, b->l);
            upd(b);
            return b;
        }
    }

    pair<Node*, Node*> split(Node *t, int x)
    {
        if (!t) return {0, 0};
        if (t->x < x)
        {
            auto p = split(t->r, x);
            t->r = p.fi;
            upd(t);
            return {t, p.se};
        }
        else
        {
            auto p = split(t->l, x);
            t->l = p.se;
            upd(t);
            return {p.fi, t};
        }
    }

    void add(Node *&t, int x)
    {
        auto p = split(t, x);
        t = merge(p.fi, merge(new Node(x), p.se));
    }

    void rem(Node *&t, int x)
    {
        if (!t) return;
        if (t->x == x)
        {
            t = merge(t->l, t->r);
            return;
        }
        if (t->x < x)
            rem(t->r, x);
        else
            rem(t->l, x);
        upd(t);
    }

    int count_geq(Node *&t, int x)
    {
        auto p = split(t, x);
        int ans = sz(p.se);
        t = merge(p.fi, p.se);
        return ans;
    }
}

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    bool chain = M == N - 1;
    bool binary_tree = M == N - 1;
    for (int i = 1; i <= M; ++i)
    {
        cin >> eV[i] >> eU[i] >> eF[i];
        chain &= eV[i] == i && eU[i] == i + 1;
        binary_tree &= eU[i] == i + 1 && eV[i] == eU[i] / 2;
    }
    int Q;
    cin >> Q;
    bool all_2 = true;
    for (int t = 1; t <= Q; ++t)
    {
        cin >> qT[t] >> qI[t] >> qF[t];
        all_2 &= qT[t] == 2;
    }
    if (N <= 1000 && M <= 1000 && Q <= 10000)
    {
        for (int i = 1; i <= M; ++i)
        {
            int v = eV[i];
            int u = eU[i];
            G[v].emplace_back(u, i);
            G[u].emplace_back(v, i);
        }
        bool used[N + 1];
        function< int(int, int) > dfs = [&](int v, int my_f) -> int
        {
            used[v] = true;
            int sz = 1;
            for (pii p : G[v])
            {
                int u = p.fi;
                int f = eF[p.se];
                if (my_f <= f)
                {
                    if (!used[u])
                    {
                        sz += dfs(u, my_f);
                    }
                }
            }
            return sz;
        };
        for (int t = 1; t <= Q; ++t)
        {
            if (qT[t] == 1)
                eF[qI[t]] = qF[t];
            else
            {
                int v0 = qI[t];
                int my_f = qF[t];
                memset(used, 0, sizeof(used));
                cout << dfs(v0, my_f) << '\n';
            }
        }
        exit(0);
    }
    if (chain)
    {
        const int logN = 16;
        const int NN = 1 << logN;
        int mn[2 * NN];
        memset(mn, 0x3f, sizeof(mn));
        for (int i = 0; i < N - 1; ++i)
            mn[i + NN] = eF[i + 1];
        for (int v = NN - 1; v >= 1; --v)
            mn[v] = min(mn[v << 1], mn[v << 1 | 1]);
        auto rmq = [&](int l, int r) -> int
        {
            int ans = INF32;
            l += NN;
            r += NN;
            while (l <= r)
            {
                if (l & 1)  chkmin(ans, mn[l++]);
                if (~r & 1) chkmin(ans, mn[r--]);
                l >>= 1;
                r >>= 1;
            }
            return ans;
        };
        for (int t = 1; t <= Q; ++t)
        {
            if (qT[t] == 1)
            {
                int i = qI[t] - 1;
                int x = qF[t];
                i += NN;
                mn[i] = x;
                for (i >>= 1; i >= 1; i >>= 1)
                    mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
            }
            else
            {
                int i = qI[t] - 1;
                int my_f = qF[t];
                int bg, en;
                {
                    int l = -1;
                    int r = i;
                    while (r - l > 1)
                    {
                        int mid = (l + r) >> 1;
                        if (rmq(mid, i - 1) >= my_f)
                            r = mid;
                        else
                            l = mid;
                    }
                    bg = r;
                }
                {
                    int l = i;
                    int r = N;
                    while (r - l > 1)
                    {
                        int mid = (l + r) >> 1;
                        if (rmq(i, mid - 1) >= my_f)
                            l = mid;
                        else
                            r = mid;
                    }
                    en = l;
                }
                cout << en - bg + 1 << '\n';
            }
        }
        exit(0);
    }
    if (all_2)
    {
        int dsu[N + 1];
        memset(dsu, 255, sizeof(dsu));
        function< int(int) > gt = [&](int v) -> int
        {
            return dsu[v] < 0 ? v : dsu[v] = gt(dsu[v]);
        };
        function< void(int, int) > un = [&](int a, int b)
        {
            a = gt(a);
            b = gt(b);
            if (a == b) return;
            if (-dsu[a] > -dsu[b]) swap(a, b);
            dsu[b] += dsu[a];
            dsu[a] = b;
        };
        int e_ord[M];
        iota(e_ord, e_ord + M, 1);
        sort(e_ord, e_ord + M, [&](int e1, int e2) -> bool
        {
            return eF[e1] > eF[e2];
        });
        int q_ord[Q];
        iota(q_ord, q_ord + Q, 1);
        sort(q_ord, q_ord + Q, [&](int q1, int q2) -> bool
        {
            return qF[q1] > qF[q2];
        });
        int ans[Q + 1];
        int ptr = 0;
        for (int qii = 0; qii < Q; ++qii)
        {
            int t = q_ord[qii];
            int my_f = qF[t];
            int v = qI[t];
            while (ptr < M && eF[e_ord[ptr]] >= my_f)
            {
                int e = e_ord[ptr++];
                un(eV[e], eU[e]);
            }
            ans[t] = -dsu[gt(v)];
        }
        for (int t = 1; t <= Q; ++t)
            cout << ans[t] << '\n';
        exit(0);
    }
    if (binary_tree)
    {
        int F[N + 1];
        for (int i = 1; i <= N - 1; ++i)
            F[i + 1] = eF[i];
        treap::Node* subtr[N + 1];
        memset(subtr, 0, sizeof(subtr));
        auto add = [&](int v)
        {
            int cur_f = INF32;
            for (; v >= 1; v >>= 1)
            {
                treap::add(subtr[v], cur_f);
                chkmin(cur_f, F[v]);
            }
        };
        auto rem = [&](int v)
        {
            int cur_f = F[v];
            for (; v >= 1; v >>= 1)
            {
                treap::rem(subtr[v], cur_f);
                chkmin(cur_f, F[v]);
            }
        };
        for (int v = 1; v <= N; ++v) add(v);
        for (int t = 1; t <= Q; ++t)
        {
            if (qT[t] == 1)
            {
                int v = qI[t] + 1;
                int f = qF[t];
                if (f == F[v]) continue;
                rem(v);
                F[v] = f;
                add(v);
            }
            else
            {
                int v = qI[t];
                int f = qF[t];
                while (v / 2 >= 1 && F[v] >= f) v /= 2;
                cout << treap::count_geq(subtr[v], f) << '\n';
            }
        }
    }

    return 0;
}

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