제출 #898404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898404		GrandTiger1729	Joker (BOI20_joker)	C++17	0 / 100	2066 ms	6468 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

struct DSU
{
    vector<int> rt, sz;
    vector<int> stk;
    DSU(int n)
    {
        rt.resize(n);
        iota(rt.begin(), rt.end(), 0);
        sz.resize(n, 1);
    }
    int find(int u)
    {
        if (u == rt[u])
        {
            return u;
        }
        return find(rt[u]);
    }
    bool same(int u, int v)
    {
        return find(u) == find(v);
    }
    void unite(int u, int v)
    {
        u = find(u), v = find(v);
        if (u == v)
        {
            stk.push_back(-1);
            return;
        }
        if (sz[u] > sz[v])
        {
            swap(u, v);
        }
        rt[u] = v;
        sz[v] += sz[u];
        stk.push_back(u);
    }
    void undo()
    {
        int u = stk.back();
        stk.pop_back();
        if (u == -1)
        {
            return;
        }
        int v = rt[u];
        sz[v] -= sz[u];
        rt[u] = u;
    }
};

const int B = 1, C = 3, D = 1;
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> ed(m);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        ed[i] = make_pair(u, v);
    }
    vector<int> rr(m, -1);
    for (int c = 0; c * C * B < m; c++)
    {
        int L1 = c * C * B, L2 = min(m, (c + 1) * C * B);
        int R = -1;
        DSU dsu(2 * n);
        {
            for (int i = 0; i < L1; i++)
            {
                auto [u, v] = ed[i];
                dsu.unite(u, v + n);
                dsu.unite(u + n, v);
                if (dsu.same(u, v))
                {
                    R = i;
                    break;
                }
            }
            if (R != -1)
            {
                break;
            }
            for (int i = L1; i < L2; i++)
            {
                auto [u, v] = ed[i];
                dsu.unite(u, v + n);
                dsu.unite(u + n, v);
                if (dsu.same(u, v))
                {
                    R = i;
                    break;
                }
            }
            if (R == -1)
            {
                R = m - 1;
                while (R >= L2)
                {
                    auto [u, v] = ed[R];
                    dsu.unite(u, v + n);
                    dsu.unite(u + n, v);
                    if (dsu.same(u, v))
                    {
                        dsu.undo();
                        dsu.undo();
                        break;
                    }
                    R--;
                }
                for (int i = m - 1; i > R; i--)
                {
                    dsu.undo();
                    dsu.undo();
                }
                for (int i = L1; i < L2; i++)
                {
                    dsu.undo();
                    dsu.undo();
                }
            }
            else
            {
                for (int i = L1; i <= R; i++)
                {
                    dsu.undo();
                    dsu.undo();
                }
                R = m - 1;
            }
            for (int i = m - 1; i > R; i--)
            {
                auto [u, v] = ed[i];
                dsu.unite(u, v + n);
                dsu.unite(u + n, v);
            }
        }
        for (int d = (L2 - 1 - L1) / (B * D); d >= 0; d--)
        {
            int ll = L1 + d * B * D;
            for (int i = L1; i < ll; i++)
            {
                auto [u, v] = ed[i];
                dsu.unite(u, v + n);
                dsu.unite(u + n, v);
            }
            for (int i = ll; i < L2; i++)
            {
                auto [u, v] = ed[i];
                dsu.unite(u, v + n);
                dsu.unite(u + n, v);
            }
            int r2 = R;
            for (int b = (L2 - 1 - ll) / B; b >= 0; b--)
            {
                int l1 = ll + b * B, l2 = min(L2, l1 + B);
                for (int i = l1; i < l2; i++)
                {
                    dsu.undo();
                    dsu.undo();
                }
                for (int i = R; i > r2; i--)
                {
                    auto [u, v] = ed[i];
                    dsu.unite(u, v + n);
                    dsu.unite(u + n, v);
                }
                int r = r2;
                bool f = 0;
                for (int i = r; i >= l1; i--)
                {
                    int l = l1;
                    while (l < l2 && l <= i)
                    {
                        auto [u, v] = ed[l];
                        dsu.unite(u, v + n);
                        dsu.unite(u + n, v);
                        if (dsu.same(u, v))
                        {
                            break;
                        }
                        l++;
                    }
                    rr[i] = max(rr[i], l);
                    l = min(l, l2 - 1);
                    l = min(l, i);
                    for (int j = l1; j <= l; j++)
                    {
                        dsu.undo();
                        dsu.undo();
                    }
                    auto [u, v] = ed[i];
                    dsu.unite(u, v + n);
                    dsu.unite(u + n, v);
                    if (dsu.same(u, v))
                    {
                        r2 = i;
                        f = 1;
                        break;
                    }
                }
                if (!f)
                {
                    r2 = l1;
                }
                for (int i = r2; i <= R; i++)
                {
                    dsu.undo();
                    dsu.undo();
                }
            }
            for (int i = L1; i < ll; i++)
            {
                dsu.undo();
                dsu.undo();
            }
            for (int i = r2 + 1; i <= R; i++)
            {
                auto [u, v] = ed[i];
                dsu.unite(u, v + n);
                dsu.unite(u + n, v);
            }
            R = r2;
        }
    }
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        l--, r--;
        cout << (rr[r] >= l ? "NO" : "YES") << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29