Submission #765580

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
765580	2023-06-24T21:15:13 Z	adrilen	Joker (BOI20_joker)	C++17	25 / 100	71 ms	13268 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
            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	0 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 11
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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 11
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	68 ms	10988 KB	Output is correct
4	Correct	70 ms	13268 KB	Output is correct
5	Correct	69 ms	10552 KB	Output is correct
6	Correct	67 ms	10968 KB	Output is correct
7	Correct	67 ms	10872 KB	Output is correct
8	Correct	65 ms	10560 KB	Output is correct
9	Correct	68 ms	11084 KB	Output is correct
10	Correct	70 ms	12244 KB	Output is correct
11	Correct	68 ms	10944 KB	Output is correct
12	Correct	70 ms	11912 KB	Output is correct
13	Correct	68 ms	9976 KB	Output is correct
14	Correct	69 ms	10432 KB	Output is correct
15	Correct	71 ms	11384 KB	Output is correct
16	Correct	71 ms	12152 KB	Output is correct