Submission #475784

#	Time	Username	Problem	Language	Result	Execution time	Memory
475784		blue	Joker (BOI20_joker)	C++17	14 / 100	2096 ms	6620 KiB

Joker

#include <iostream>
#include <vector>
#include <stack>
#include <cassert>
using namespace std;

struct disjoint_set
{
    int N;

    vector<int> parent;
    vector<int> parent_edge;

    vector<int> subtree;

    stack<int> ops;
    stack<bool> bipartite;

    disjoint_set()
    {
        ;
    }

    disjoint_set(int N_)
    {
        N = N_;
        parent = vector<int>(1+N);
        parent_edge = vector<int>(1+N);
        subtree = vector<int>(1+N);

        for(int i = 0; i <= N; i++)
        {
            parent[i] = i;
            parent_edge[i] = 0;
            subtree[i] = 1;
        }

        ops.push(0);
        bipartite.push(1);
    }

    void join(int u, int v)
    {
        int opp = 1;

        while(u != parent[u])
        {
            opp ^= parent_edge[u];
            u = parent[u];
        }

        while(v != parent[v])
        {
            opp ^= parent_edge[v];
            v = parent[v];
        }

        if(u == v)
        {
            ops.push(0);
            if(bipartite.top())
            {
                if(opp == 0) bipartite.push(1);
                else bipartite.push(0);
            }
            else bipartite.push(0);
        }
        else
        {
            if(subtree[u] < subtree[v]) swap(u, v);
            parent[v] = u;
            parent_edge[v] = opp;

            subtree[u] += subtree[v];

            ops.push(v);
            bipartite.push( bipartite.top() );
        }
    }

    void rollback()
    {
        int u = ops.top();

        ops.pop();
        bipartite.pop();

        subtree[ parent[u] ] -= subtree[u];
        parent[u] = u;
        parent_edge[u] = 0;
    }

    bool is_bipartite()
    {
        return bipartite.top();
    }
};

const int maxN = 200'000;
const int maxM = 200'000;

int N, M, Q;

vector<int> u(1+maxM), v(1+maxM);

int main()
{
    cin >> N >> M >> Q;

    for(int j = 1; j <= M; j++) cin >> u[j] >> v[j];

    for(int q = 1; q <= Q; q++)
    {
        disjoint_set DSU(N);
        int l, r;
        cin >> l >> r;
        for(int i = 1; i <= M; i++)
        {
            if(i < l || r < i)
                DSU.join(u[i], v[i]);
        }

        if(DSU.is_bipartite()) cout << "NO\n";
        else cout << "YES\n";
    }
}

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