Submission #1265833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265833		cpismylifeOwO	Joker (BOI20_joker)	C++20	100 / 100	199 ms	15532 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

struct Edge
{
    int u, v;
};

int n, m, q;
Edge edges[MaxN];

void Inp()
{
    cin >> n >> m >> q;
    for (int x = 1; x <= m; x++)
    {
        cin >> edges[x].u >> edges[x].v;
    }
}

struct History
{
    int u, p, sz, val;
    bool avl;

    History(int _u, int _p, int _sz, int _val, bool _avl)
    {
        u = _u;
        p = _p;
        sz = _sz;
        val = _val;
        avl = _avl;
    }
};

int parents[MaxN];
int sz[MaxN];
int val[MaxN];
bool avl;
vector<History> history;

int FindSet(int p)
{
    if (parents[p] == p)
    {
        return p;
    }
    return FindSet(parents[p]);
}

int FindVal(int p)
{
    if (parents[p] == p)
    {
        return val[p];
    }
    return FindVal(parents[p]) ^ val[p];
}

void UnionSet(int a, int b)
{
    int aval = FindVal(a), bval = FindVal(b);
    a = FindSet(a);
    b = FindSet(b);
    history.push_back(History(a, parents[a], sz[a], val[a], avl));
    history.push_back(History(b, parents[b], sz[b], val[b], avl));
    if (a == b)
    {
        avl |= (aval == bval);
        return;
    }
    if (sz[a] < sz[b])
    {
        swap(a, b);
        swap(aval, bval);
    }
    parents[b] = a;
    sz[a] += sz[b];
    val[b] ^= aval ^ bval ^ 1;
}

void RollBack()
{
    for (int x = 0; x < 2; x++)
    {
        if (!history.empty())
        {
            parents[history.back().u] = history.back().p;
            sz[history.back().u] = history.back().sz;
            val[history.back().u] = history.back().val;
            avl = history.back().avl;
            history.pop_back();
        }
    }
}

int res[MaxN];

void PBS(int l, int r, int lq, int rq)
{
    //cout << l << " " << r << " " << lq << " " << rq << "\n";
    if (l > r || lq > rq)
    {
        return;
    }
    int mid = (l + r) / 2;
    for (int x = mid; x <= r; x++)
    {
        UnionSet(edges[x].u, edges[x].v);
    }
    int p = min(mid, rq + 1);
    for (int x = lq; x <= min(rq, mid - 1); x++)
    {
        UnionSet(edges[x].u, edges[x].v);
        if (avl)
        {
            p = x;
            break;
        }
    }
    for (int x = p; x <= rq; x++)
    {
        res[x] = mid;
    }
    if (p < min(mid, rq + 1))
    {
        RollBack();
    }
    for (int x = p - 1; x >= lq; x--)
    {
        RollBack();
    }
    for (int x = r; x >= mid; x--)
    {
        RollBack();
    }
    for (int x = lq; x < p; x++)
    {
        UnionSet(edges[x].u, edges[x].v);
    }
    PBS(mid + 1, r, p, rq);
    for (int x = p - 1; x >= lq; x--)
    {
        RollBack();
    }
    for (int x = mid; x <= r; x++)
    {
        UnionSet(edges[x].u, edges[x].v);
    }
    PBS(l, mid - 1, lq, p - 1);
    for (int x = r; x >= mid; x--)
    {
        RollBack();
    }
}

void Exc()
{
    avl = false;
    history.clear();
    for (int x = 1; x <= n; x++)
    {
        res[x] = x;
        parents[x] = x;
        sz[x] = 1;
        val[x] = 0;
    }
    for (int x = 1; x <= m; x++)
    {
        UnionSet(edges[x].u, edges[x].v);
    }
    if (!avl)
    {
        for (int x = 1; x <= q; x++)
        {
            int l, r;
            cin >> l >> r;
            cout << "NO\n";
        }
        return;
    }
    for (int x = 1; x <= n; x++)
    {
        parents[x] = x;
        sz[x] = 1;
        val[x] = 0;
    }
    avl = false;
    history.clear();
    PBS(1, m, 1, m);
    for (int x = 1; x <= n; x++)
    {
        parents[x] = x;
        sz[x] = 1;
        val[x] = 0;
    }
    avl = false;
    history.clear();
    for (int x = 1; x <= m; x++)
    {
        UnionSet(edges[x].u, edges[x].v);
        if (avl)
        {
            for (int y = x; y <= m; y++)
            {
                res[y] = m + 1;
            }
            break;
        }
    }
    for (int x = 1; x <= n; x++)
    {
        parents[x] = x;
        sz[x] = 1;
        val[x] = 0;
    }
    avl = false;
    history.clear();
    for (int x = m; x > 0; x--)
    {
        UnionSet(edges[x].u, edges[x].v);
        if (avl)
        {
            res[0] = x;
            break;
        }
    }
    for (int x = 1; x <= q; x++)
    {
        int l, r;
        cin >> l >> r;
        if (res[l - 1] > r)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
}

int main()
{
    //freopen("JOKER.INP", "r", stdin);
    //freopen("JOKER.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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