oj.uz

Submission #898216

# Submission time Handle Problem Language Result Execution time Memory
898216 2024-01-04T11:38:09 Z GrandTiger1729 Joker (BOI20_joker) C++17
0 / 100
 919 ms 6288 KB 
#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 && !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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 919 ms 6288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -