제출 #765497

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765497		adrilen	Joker (BOI20_joker)	C++17	49 / 100	2045 ms	9848 KiB

Joker

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 2> arr;
typedef array<int, 3> arrr;

struct UnionFind {
    vector <int> par; // >= 0 -> ind, < 0 -> siz
    vector <int> parity;
    vector <int> siz;

    vector <arr> history;

    UnionFind(int n, int m)
    {
        par.assign(n, -1);
        parity.assign(n, 0);
        siz.assign(n, 1);
    }

    pii fnd(int p)
    {
        if (par[p] < 0) return {p, 0};

        pii o = fnd(par[p]);
        o.second ^= parity[p];
        return o;
    }

    bool uni(int a, int b) // Return whether this will be an odd cycle
    {
        int a_parity, b_parity;
        tie(a, a_parity) = fnd(a);
        tie(b, b_parity) = fnd(b);

        if (a == b)
        {
            history.emplace_back(arr{-1, -1});
            if (a_parity == b_parity)
            {
                // Odd cycle
                return true;
            } else {
                return false;
            }
        }


        if (siz[a] < siz[b]) swap(a, b);
        // a > b
        // b will be merged into b

        siz[a] += siz[b];
        parity[b] = a_parity ^ b_parity ^ 1;
        par[b] = a;

        history.emplace_back(arr{a, b});
        return false;
    }

    void undo()
    {
        arr p = history.back();
        history.pop_back();
        if (p[0] == -1) return ;

        siz[p[0]] -= siz[p[1]];
        parity[p[1]] = 0;
        par[p[1]] = -1;
    }
} ;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m, q;
    cin >> n >> m >> q;

    vector<arr> edges(m);
    for (auto &i : edges) {
        cin >> i[0] >> i[1];
        i[0]--, i[1]--;
    }

    int b = 0;
    vector <arrr> queries(q);
    for (auto &i : queries)
    {
        cin >> i[0] >> i[1];
        i[0]--, i[1]--;
        i[2] = b++;
    }

    // Starting with the queries the furthest to the right
    sort(queries.begin(), queries.end(), [] (const auto &lhs, const auto &rhs)
    {
        if (lhs[1] == rhs[1]) return lhs[0] > rhs[0];
        return lhs[1] > rhs[1];
    });

    vector <int> output(q);

    UnionFind Graph(n, m);

    // const int max_range = 200;

    bool have_found_cycle = false, this_cycle;

    auto right_edge = edges.end() - 1;
    auto left_edge = edges.begin();
    for (auto &i : queries)
    {
        if (have_found_cycle) {
            output[i[2]] = true;
            continue;
        }

        // The right side

        // Check if the right amount
        while (right_edge - edges.begin() > i[1]) {
            if (Graph.uni((*right_edge)[0], (*right_edge)[1])) {
                // All queries after this will be true
                have_found_cycle = true;
            }
            right_edge--;
        }

        // The left side
        assert(left_edge == edges.begin());
        this_cycle = false;
        while (left_edge - edges.begin() < i[0])
        {
            if (Graph.uni((*left_edge)[0], (*left_edge)[1])) {
                this_cycle = true;
                left_edge++;
                break;
            }
            left_edge++;
        }
        
        output[i[2]] = (this_cycle || have_found_cycle);

        // Remove last edges
        while (left_edge != edges.begin())
        {
            Graph.undo();
            left_edge--;
        }

    }

    for (auto &i : output) cout << (i ? "YES" : "NO") << "\n";

    // for (auto &i : queries)
    // {
    //     cout << (i[1] < a ? "YES" : "NO") << "\n";
    // }
}

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