Submission #475823

#	Time	Username	Problem	Language	Result	Execution time	Memory
475823		blue	Joker (BOI20_joker)	C++17	14 / 100	2087 ms	6576 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);
    }

    int root(int u)
    {
        while(parent[u] != u)
            u = parent[u];
        return u;
    }

    void join(int u, int v)
    {
        // cerr << "join " << u << ' ' << v << '\n';
        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()
    {
        // cerr << "rollback\n";
        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);

vector<int> minR(1+maxN, 0);
//the minimum value of R so that if the roads i, ... R are blocked the graph is bipartite

disjoint_set DSU;

int L;
int R;

void expand_right()
{
    R++;
    DSU.rollback();
}

void contract_right()
{
    R--;
    DSU.join(u[R+1], v[R+1]);
}

void expand_left()
{
    L--;
    DSU.rollback();
}

void contract_left()
{
    L++;
    DSU.join(u[L-1], v[L-1]);
}

bool flag = 0;

void dbg(string s)
{
    if(flag) cerr << s << '\n';
}

void dbg(int i)
{
    if(flag) cerr << "dbg " << i << '\n';
}

void dbg(string s, int i)
{
    if(flag) cerr << s << " " << i << '\n';
}

void solve(int l1, int l2, int r1, int r2) // [L, R] == [l1, r2] at the beginning
{
    // cerr << "random solve\n";
    // if(l1 <= 6 && 6 <= l2)
    //     cerr << "solve " << l1 << ' ' << l2 << ' ' << r1 << ' ' << r2 << '\n';
    // for(int i = 1; i <= M; i++) cerr << minR[i] << ' ';
    // cerr << '\n';
    assert(L == l1);
    assert(R == r2);
    int lmid = (l1+l2)/2;
    int rmid;

    flag = 0;
    dbg(lmid);

    if(!DSU.is_bipartite())
    {
        dbg("check\n");
        // cerr << "check\n";
        // cerr << l1 << ' ' << l2 << " emergency\n";
        // cerr << lmid << '\n';
        // cerr << "M = " << M << '\n';
        for(int i = lmid; i <= l2; i++)
        {
            minR[i] = M+1;
            // cerr << minR[i] << '\n';
        }
        if(l1 <= lmid-1)
        {
            solve(l1, lmid-1, r1, r2); //ADJUST L AND R!!!!! -> not necessary
        }
        return;
    }

    // cerr <<
    dbg("L", L);
    dbg("R", R);
    for(int i = 1; i <= N; i++) dbg(to_string(i), DSU.root(i));
    dbg(DSU.is_bipartite());

    while(L < lmid)
        contract_left();

    if(!DSU.is_bipartite())
    {
        while(l1 < L)
            expand_left();
        dbg("check\n");
        // cerr << "check\n";
        // cerr << l1 << ' ' << l2 << " emergency\n";
        // cerr << lmid << '\n';
        // cerr << "M = " << M << '\n';
        for(int i = lmid; i <= l2; i++)
        {
            minR[i] = M+1;
            // cerr << minR[i] << '\n';
        }
        if(l1 <= lmid-1)
        {
            solve(l1, lmid-1, r1, r2); //ADJUST L AND R!!!!! -> not necessary
        }
        return;
    }

    rmid = r2;
    while(DSU.is_bipartite())
    {
        rmid = min(rmid, R);
        contract_right();
    }

    minR[lmid] = rmid;

    while(R < r2)
        expand_right();
    while(l1 < L)
        expand_left();

    assert(L == l1 && R == r2);

    if(l1 <= lmid-1)
    {
        while(rmid < R)
            contract_right();

        assert(L == l1 && R == rmid);
        solve(l1, lmid-1, r1, rmid);

        while(R < r2)
            expand_right();
    }

    if(lmid+1 <= l2)
    {
        while(L < lmid+1)
            contract_left();

        assert(L == lmid+1 && R == r2);
        solve(lmid+1, l2, rmid, r2);

        while(l1 < L)
            expand_left();
    }

    assert(L == l1 && R == r2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> Q;

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

    DSU = disjoint_set(N);

    disjoint_set temp(N);
    for(int j = 1; j <= M; j++) temp.join(u[j], v[j]);
    if(temp.is_bipartite())
    {
        int x;
        for(int u = 1; u <= Q; u++)
        {
            cin >> x >> x;
            cout << "NO\n";
        }
        return 0;
    }

    L = 1;
    R = M;
    solve(1, min(2000,M), 1, M);

    // for(int j = 1; j <= M; j++) cerr << minR[j] << ' ';
    // cerr << '\n';

    for(int q = 1; q <= Q; q++)
    {
        int l, r;
        cin >> l >> r;

        if(minR[l] <= r) cout << "NO\n"; //bipartite
        else cout << "YES\n"; //not bipartite
    }
}

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