제출 #898266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898266		GrandTiger1729	Joker (BOI20_joker)	C++17	6 / 100	2053 ms	9868 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 = 450;
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 b = 0; b * B < m; b++)
    {
        int l1 = b * B, l2 = min(m, (b + 1) * 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 i = r; i >= l1; i--)
        {
            int l = l1;
            while (l < l2 && l <= i && l < 210)
            {
                auto [u, v] = ed[l];
                dsu.unite(u, v + n);
                dsu.unite(u + n, v);
                if (dsu.same(u, v))
                {
                    break;
                }
                l++;
            }
            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))
            {
                break;
            }
        }
    }
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        l--, r--;
        cout << (rr[r] >= l ? "NO" : "YES") << '\n';
    }
    return 0;
}

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