Submission #765451

#	Time	Username	Problem	Language	Result	Execution time	Memory
765451		adrilen	Joker (BOI20_joker)	C++17	25 / 100	65 ms	6572 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_size; // >= 0 -> ind, < 0 -> siz
    vector <int> parity;

    bool has_odd_cycle;

    UnionFind(int n, int m)
    {
        par_size.assign(n, -1);
        parity.assign(n, 0);
        has_odd_cycle = false;
    }

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

        pii o = fnd(par_size[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)
        {
            if (a_parity == b_parity)
            {
                // Odd cycle
                return true;
            } else {
                return false;
            }
        }


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

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

        return false;
    }


} ;


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

    UnionFind Graph(n, m);

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

    reverse(edges.begin(), edges.end());

    int a = 0;
    for (auto &i : edges)
    {
        if (Graph.uni(i[0], i[1])) break;
        a++;
    }

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


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

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