Submission #898232

#	Time	Username	Problem	Language	Result	Execution time	Memory
898232		GrandTiger1729	Joker (BOI20_joker)	C++17	41 / 100	580 ms	12372 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);
    DSU dsu(2 * n);
    bool f = 0;
    for (int r = m - 1; r >= 0; r--)
    {
        if (f)
        {
            continue;
        }
        bool f2 = 0;
        int l = 0;
        while (l <= r && l <= 210)
        {
            auto [u, v] = ed[l];
            dsu.unite(u, v + n);
            dsu.unite(u + n, v);
            if (dsu.same(u, v))
            {
                for (int j = 0; j <= l; j++)
                {
                    dsu.undo();
                    dsu.undo();
                }
                f2 = 1;
                break;
            }
            l++;
        }
        rr[r] = l;
        if (!f2)
        {
            for (int j = 0; j < l; j++)
            {
                dsu.undo();
                dsu.undo();
            }
        }
        auto [u, v] = ed[r];
        dsu.unite(u, v + n);
        dsu.unite(u + n, v);
        if (dsu.same(u, v))
        {
            f = 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 && !dsu.same(ed[i].first, ed[i].second); 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))
    //             {
    //                 for (int j = l1; j <= l; j++)
    //                 {
    //                     dsu.undo();
    //                     dsu.undo();
    //                 }
    //                 break;
    //             }
    //             l++;
    //         }
    //         rr[i] = l;
    //         auto [u, v] = ed[i];
    //         dsu.unite(u, v + n);
    //         dsu.unite(u + n, v);
    //     }
    // }
    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: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29