Submission #765575

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
765575	2023-06-24T21:01:50 Z	adrilen	Joker (BOI20_joker)	C++17	25 / 100	86 ms	17460 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);

    UnionFind Graph(n, m);

    int c = 0;
    for (auto &y : query_groups)
    {
        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	0 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	0 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	0 ms	212 KB	Output is correct
3	Correct	71 ms	14296 KB	Output is correct
4	Correct	73 ms	17460 KB	Output is correct
5	Correct	73 ms	14696 KB	Output is correct
6	Correct	69 ms	14908 KB	Output is correct
7	Correct	86 ms	15012 KB	Output is correct
8	Correct	66 ms	13944 KB	Output is correct
9	Correct	68 ms	14424 KB	Output is correct
10	Correct	82 ms	15808 KB	Output is correct
11	Correct	72 ms	14900 KB	Output is correct
12	Correct	72 ms	15936 KB	Output is correct
13	Correct	70 ms	13888 KB	Output is correct
14	Correct	70 ms	14404 KB	Output is correct
15	Correct	71 ms	15428 KB	Output is correct
16	Correct	79 ms	16188 KB	Output is correct