Submission #765577

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
765577	2023-06-24T21:10:47 Z	adrilen	Joker (BOI20_joker)	C++17	25 / 100	76 ms	13300 KB

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;

constexpr int sqrt_n = 478;

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)
    {
        return lhs[0] < rhs[0];
    });

    vector <int> min_start(sqrt_n, 2e9);
    vector <vector <arrr>> query_groups(sqrt_n);
    for (auto &i : queries)
    {
        query_groups[i[0] / sqrt_n].emplace_back(i);
        min_start[i[0] / sqrt_n] = min(min_start[i[0] / sqrt_n], i[0]);
    }

    for (auto &i : query_groups) sort(i.begin(), i.end(), [] (const auto &lhs, const auto &rhs) {
        return lhs[1] > rhs[1];
    });
    

    vector <int> output(q);


    int c = 0;
    for (auto &y : query_groups)
    {
        UnionFind Graph(n, m);

        if (y.empty()) break;
        bool have_found_cycle = false, this_cycle;

        auto right_edge = edges.end() - 1;
        auto left_edge = edges.begin() + min_start[c];
        for (auto &i : y)
        {
            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--;
            }

        }
        c++;
    }

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

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

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Runtime error	1 ms	468 KB	Execution killed with signal 6
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Runtime error	1 ms	468 KB	Execution killed with signal 6
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	70 ms	10968 KB	Output is correct
4	Correct	73 ms	13300 KB	Output is correct
5	Correct	72 ms	10496 KB	Output is correct
6	Correct	68 ms	10992 KB	Output is correct
7	Correct	68 ms	10872 KB	Output is correct
8	Correct	66 ms	10632 KB	Output is correct
9	Correct	65 ms	11132 KB	Output is correct
10	Correct	69 ms	12240 KB	Output is correct
11	Correct	68 ms	10884 KB	Output is correct
12	Correct	70 ms	11844 KB	Output is correct
13	Correct	71 ms	9976 KB	Output is correct
14	Correct	72 ms	10460 KB	Output is correct
15	Correct	76 ms	11480 KB	Output is correct
16	Correct	71 ms	12152 KB	Output is correct