Submission #765252

#	Time	Username	Problem	Language	Result	Execution time	Memory
765252		adrilen	Joker (BOI20_joker)	C++17	0 / 100	86 ms	11148 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;

constexpr int maxn = 2e5;

int siz[maxn] = { 0 }, par[maxn] = { 0 }, parity[maxn] = { 0 };
bool cycle[maxn] = { 0 };


int fnd(int p)
{
    if (p == par[p]) return p;
    return fnd(par[p]);
}

int fnd_parity(int p, int pari)
{
    if (p == par[p]) return pari;

    return fnd_parity(par[p], pari ^ parity[par[p]]);
}

bool odd_cycle = false;

void uni(int a, int b)
{
    int aa = fnd(a), bb = fnd(b);

    if (aa == bb) {
        if (fnd_parity(a, parity[a]) == fnd_parity(b, parity[b])) {
            // Odd cycle
            // cout << "\n";
            // cout << a << " " << b << " odd cycle\n";
            cycle[aa] = true;
            odd_cycle = true;
        } else {
            // Not odd cycle
        }
        return ;
    }

    if (siz[aa] > siz[bb]) {
        swap(a, b);
        swap(aa, bb);
    }
    
    // b > a
    parity[aa] = parity[a] ^ parity[b] ^ 1;
    par[aa] = bb;
    siz[bb] += siz[aa];

}

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

    for (int i = 0; i < n; i++) {
        siz[i] = 1;
        par[i] = i;
    }

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

        cin >> queries[i][0] >> queries[i][1];
        queries[i][0]--, queries[i][1]--;
        queries[i][2] = i;
    }
    

    vector <bool> output(q);
 
    reverse(edges.begin(), edges.end());
    sort(queries.begin(), queries.end(), greater<arrr>());

    auto it = queries.begin();

    int a = 0;
    for (auto &i : edges)
    {
        while (it != queries.end() && m - 1 - (*it)[1] == a)
        {
            // cout << (*it)[2] << "\n";
            output[(*it)[2]] = odd_cycle;
            it++;
        }

        uni(i[0], i[1]);


        // cout << a << " " << (odd_cycle ? "YES" : "NO") << "\n";
        a++;
    }


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



    // cout << par[0] << "\n";
    // for (int i = 0; i < n; i++) {
    //     cout << parity[i] << " ";
    // }
    // cout << "\n";
    // for (int i = 0; i < n; i++) {
    //     cout << par[i] << " ";
    // }
    // cout << "\n";
    
}

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