제출 #216434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216434		usachevd0	다리 (APIO19_bridges)	C++14	43 / 100	315 ms	9592 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; }

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];

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;
    for (int i = 1; i <= M; ++i)
    {
        cin >> eV[i] >> eU[i] >> eF[i];
        chain &= eV[i] == i && eU[i] == i + 1;
    }
    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);
    }

    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