Submission #477115

#	Time	Username	Problem	Language	Result	Execution time	Memory
477115		blue	Joker (BOI20_joker)	C++17	100 / 100	566 ms	22848 KiB

Joker

#include <iostream>
#include <vector>
#include <stack>
#include <cassert>
using namespace std;
 
void asrt(bool b)
{
    if(!b)
    {
        cerr << "failed!\n";
        while(1);
    }
}
 
struct disjoint_set
{
    int N;
    vector<int> parent;
    vector<int> parent_edge; //the color of this node is the xor of path up to parent
    vector<int> subtree;

    vector<int> op_node = vector<int>(1, 0);
    vector<int> op_oldparent = vector<int>(1, 0);
    vector<int> op_oldxor = vector<int>(1, 0);
    vector<int> op_time = vector<int>(1, 0);
    vector<bool> bipartite = vector<bool>(1, 1);
    vector<bool> subtree_change = vector<bool>(1, 0);

    int curr_time = 0;

    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 = 1; i <= N; i++)
        {
            parent[i] = i;
            parent_edge[i] = 0;
            subtree[i] = 1;
        }
    }

    pair<int, int> root(int u) //first = root, second = xor of root and u
    {
        int v = u;
        int edg = 0;
        while(parent[v] != v)
        {
            edg ^= parent_edge[v];
            v = parent[v];
        }

        if(v == u || v == parent[u]) return make_pair(parent[u], edg);

        op_node.push_back(u);
        op_oldparent.push_back(parent[u]);
        op_oldxor.push_back(parent_edge[u]);
        op_time.push_back(curr_time);
        bipartite.push_back(bipartite.back());
        subtree_change.push_back(0);

        parent[u] = v;
        parent_edge[u] = edg;

        return make_pair(parent[u], parent_edge[u]);
    }

    void join(int u, int v)
    {
        curr_time++;

        pair<int, int> U = root(u);
        pair<int, int> V = root(v);

        if(U.first == V.first)
        {
            op_node.push_back(0);
            op_oldparent.push_back(0);
            op_oldxor.push_back(0);
            op_time.push_back(curr_time);

            if(U.second == V.second)
            {
                bipartite.push_back(0);
            }
            else
            {
                bipartite.push_back(bipartite.back());
            }

            subtree_change.push_back(0);
        }
        else
        {
            // cerr << "case 2\n";
            if(subtree[U.first] < subtree[V.first]) swap(U, V);
            // cerr << U.first << ' ' << V.first << '\n';

            op_node.push_back(V.first);
            op_oldparent.push_back(parent[V.first]);
            op_oldxor.push_back(parent_edge[V.first]);
            op_time.push_back(curr_time);
            bipartite.push_back(bipartite.back());
            subtree_change.push_back(1);

            parent[V.first] = U.first;
            parent_edge[V.first] = 1 ^ V.second ^ U.second;
            subtree[U.first] += subtree[V.first];

            // cerr << U.first << ' ' << V.first << ' ' << parent[V.first] << '\n';
        }
    }

    void rollback()
    {
        while(op_time.back() == curr_time)
        {
            int u = op_node.back();
            int v = op_oldparent.back();
            int x = op_oldxor.back();
            bool s = subtree_change.back();

            op_node.pop_back();
            op_oldparent.pop_back();
            op_oldxor.pop_back();
            op_time.pop_back();
            bipartite.pop_back();
            subtree_change.pop_back();

            if(s) subtree[ parent[u] ] -= subtree[u];
            parent[u] = v;
            parent_edge[u] = x;
        }

        curr_time--;
    }

    bool is_bipartite()
    {
        return bipartite.back();
    }
};
 
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 solve(int l1, int l2, int r1, int r2) // [L, R] == [l1, r2] at the beginning
{
    // cerr << "solve " << l1 << ' ' << l2 << ' ' << r1 << ' ' << r2 << '\n';
    bool F = 0;
    if(l1 <= 8 && 8 <= l2) F = 1;
    // assert(L == l1);
    // assert(R == r2);
    int lmid = (l1+l2)/2;
    int rmid;
 
    flag = 0;
    // dbg(lmid);
    // cerr << "hello\n";
 
    // if(F) cerr << "special solve " << l1 << ' ' << l2 << ' ' << r1 << ' ' << r2 << '\n';
 
    if(!DSU.is_bipartite())
    {
        // if(F) cerr << "!!!!\n";
        // if(!F)
        // {
        //     cerr << L << ' ' << R << '\n';
        //     cerr << "???????\n";
        //
        //
        //         cerr << "###\n";
        //
        //
        //     cerr << "DSU: ";
        //     for(int i = 1; i <= N; i++) cerr << DSU.root(i) << ' ';
        //     cerr << '\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 <<
    // for(int i = 1; i <= N; i++) dbg(to_string(i), DSU.root(i));
    // dbg(DSU.is_bipartite());
 
    while(L < lmid)
        contract_left();
 
    // if(F)cerr<<"lmid="<<lmid<<"\n";
 
    if(!DSU.is_bipartite())
    {
        while(l1 < L)
            expand_left();
        // 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;
    }
    // if(F) cerr << "check\n";
 
    rmid = r2;
    while(DSU.is_bipartite())
    {
        // cerr << "bipartite = yes\n";
        rmid = min(rmid, R);
        contract_right();
    }
    // cerr << "rmid = " << rmid << '\n';
 
    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, 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
    }
}

Compilation message (stderr)

Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:196:10: warning: variable 'F' set but not used [-Wunused-but-set-variable]
  196 |     bool F = 0;
      |          ^

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