Submission #1276509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276509		BigBadBully	Joker (BOI20_joker)	C++20	0 / 100	201 ms	327680 KiB

Joker

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int inf = 2e9;
const int maxv = 1e9;

struct dsu
{
    int n;
    vector<int> par, sz, chang;
    vector<bool> col;
    int bad = 0;
    dsu(int s)
    {
        n = s;
        par.resize(n);
        sz.resize(n, 1);
        col.resize(n, 0);
        chang.reserve(n);
        for (int i = 0; i < n; i++)
            par[i] = i;
    }
    int fnd(int x)
    {
        if (x == par[x])
            return x;
        chang.push_back(x);
        int val = fnd(par[x]);
        col[x] = col[x] ^ (val / n);
        par[x] = val % n;
        return par[x] + n * col[x];
    }
    void unite(int a, int b)
    {
        
        a = fnd(a), b = fnd(b);
        if (a==b)
            bad = 1, chang.push_back(n);
        a%=n;
        b%=n;
        if (a == b)
            return;
        chang.push_back(a), chang.push_back(b);
        if (sz[a] < sz[b])
            swap(a, b);
        col[b] = col[b] ^ (col[a] == col[b]);
        sz[a] += sz[b];
        par[b] = a;
    }
};

void solve()
{
    int n, m, q;
    cin >> n >> m >> q;
    int bl = sqrt(m);
    vector<pii> e(m);
    for (pii &x : e)
        cin >> x.ff >> x.ss, x.ff--, x.ss--;
    vector<int> ans(q);
    vector<array<int, 3>> qs(q);
    for (auto &x : qs)
        cin >> x[0] >> x[1], x[0]--, x[1]--;

    for (int i = 0; i < q; i++)
        qs[i][2] = i;
    sort(qs.begin(), qs.end(), [&](auto a, auto b)
         {
        if (a[0]<b[0])return 1;
        if(a[0]>b[0])return 0;
        if(a[1]>b[1])return 1;
        return 0; });
    vector<dsu> mile((m - 1) / bl + 1, dsu(n));
    dsu ini(n);
    {
        int i = m - 1;
        for (int cur = (m - 1) / bl; cur >= 0; cur--)
        {
            ini.chang.clear();
            mile[cur] = ini;
            for (; i >= 0 && i / bl >= cur; i--)
                ini.unite(e[i].ff, e[i].ss);
        }
    }
    auto gr = mile;
    int pr = 0;
    for (auto a : qs)
    {
        int l = a[0], r = a[1], idx = a[2];
        for (int i = pr; i < l; i++)
            for (auto &g : mile)
            {
                g.unite(e[i].ff, e[i].ss);
                g.chang.clear();
            }
        dsu &gn = mile[r / bl];
        dsu &gh = gr[r / bl];
        for (int i = r + 1; i / bl == r / bl && i < m; i++)
            gn.unite(e[i].ff, e[i].ss);

        ans[idx] = gn.bad;

        for (int x : gn.chang)
        {
            if (x == n)
                gn.bad = 0;
            else
            {
                gn.par[x] = gh.par[x];
                gn.col[x] = gh.col[x];
                gn.sz[x] = gh.sz[x];
            }
        }
        gn.chang.clear();
        pr = l;
    }
    for (int x : ans)
        cout << (x ? "YES\n" : "NO\n");
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

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