Submission #254787

#	Time	Username	Problem	Language	Result	Execution time	Memory
254787		model_code	Joker (BOI20_joker)	C++11	71 / 100	2079 ms	12640 KiB

Joker

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;


#define MAXN 200005
#define MAXM 200005
#define MAXQ 200005


int comp[MAXN], h[MAXN];
bool col_switch[MAXN];
int n_mem, mem_cv[MAXM], mem_cu[MAXM], mem_hcu[MAXM];
bool mem_swcv[MAXM];

// init DSU state
void init_dsu(int n)
{
    for(int i = 0; i < n; i++) {
        comp[i] = i;
        h[i] = 0;
        col_switch[i] = 0;
    }
    n_mem = 0;
}

// find root and color for given node
pair<int, bool> find(int v)
{
    bool col = col_switch[v];
    while (comp[v] != v) {
        v = comp[v];
        col ^= 1;
        col ^= col_switch[v];
    }
    return make_pair(v, col);
}

// merge given nodes
// silent merge if already in the same component
void merge(int v, int u)
{
    pair<int, int> ansv = find(v), ansu = find(u);
    int cv = ansv.first, cu = ansu.first;
    bool colv = ansv.second, colu = ansu.second;
    if (cv != cu) {
        // make sure to point the smaller (lower rank) set to the bigger one
        if (h[cv] > h[cu]) {
            swap(cv, cu);
            swap(v, u);
        }
        // cache operation for rollback
        mem_cv[n_mem] = cv;
        mem_cu[n_mem] = cu;
        mem_hcu[n_mem] = h[cu];
        mem_swcv[n_mem] = col_switch[cv];
        n_mem++;
        // merge and update values
        comp[cv] = cu;
        if (h[cv] == h[cu]) h[cu]++;
        col_switch[cv] = (colv != colu);
    }
    else {
        mem_cv[n_mem] = -1;
        n_mem++;
    }
}

// check how two noodes relate to each other
int check(int v, int u)
{
    pair<int, int> ansv = find(v), ansu = find(u);
    int cv = ansv.first, cu = ansu.first;
    bool colv = ansv.second, colu = ansu.second;
    if (cv != cu) return 2; // different sets
    if (colv == colu) return -1; // same set and same color (odd cycle)
    return 1; // same set, different color
}

// reset last k DSU merges
void rollback(int k)
{
    while (k--) {
        n_mem--;
        int cv = mem_cv[n_mem], cu = mem_cu[n_mem];
        bool swcv = mem_swcv[n_mem];
        if (cv == -1) continue;
        comp[cv] = cv;
        h[cu] = cu;
        col_switch[cv] = swcv;
    }
}


int N, M, Q;
int E[2][MAXM], queries[2][MAXQ], res[MAXQ];
vector<int> inds;


// solve for queries in `inds`
// must have properly set DSU state (containing all edges before current block's left edge)
void solve_for_inds(int e_left_next)
{
    int k = inds.size();

    // order queries by right index, descending
    vector<pair<int, int> > v(k);
    for (int i = 0; i < k; i++) {
        int ind = inds[i];
        v[i] = make_pair(-queries[1][ind], ind);
    }
    sort(v.begin(), v.end());

    int e_right_next = M-1, steps = 0;
    bool got_cycle = false;

    // process queries
    // * first add all edges to the right of current query window
    // * then add all edges to the left
    // * after done, rollback left-added edges
    for (int i = 0; i < k; i++) {
        int ind = v[i].second;
        int L = queries[0][ind], R = queries[1][ind];
        // add all edges to the right of current query window
        if (not got_cycle) {
            while (e_right_next > R) {
                int status = check(E[0][e_right_next], E[1][e_right_next]);
                if (status == -1) {
                    got_cycle = true;
                    break;
                }
                merge(E[0][e_right_next], E[1][e_right_next]);
                e_right_next--;
                steps++;
            }
        }
        bool got_cycle_inner = got_cycle;
        int steps_inner = 0;
        // then add all edges to the left
        if (not got_cycle_inner) {
            for (int e = e_left_next; e < L; e++) {
                int status = check(E[0][e], E[1][e]);
                if (status == -1) {
                    got_cycle_inner = true;
                    break;
                }
                merge(E[0][e], E[1][e]);
                steps_inner++;
            }
        }
        res[ind] = int(got_cycle or got_cycle_inner);
        // rollback left-added edges
        rollback(steps_inner);
    }

    // rollback all right-added edges
    rollback(steps);
}


void solve()
{
    // block size
    int B = max(int(M / sqrt(Q)), 1);

    // order queries by block index
    vector<pair<int, int> > v(Q);
    for (int i = 0; i < Q; i++) {
         v[i] = make_pair(queries[0][i] / B, i);
    }
    sort(v.begin(), v.end());

    init_dsu(N);
    int e_left_next = 0; // left pointer
    bool got_cycle = false; // once we get a (odd) cycle we just answer all following queries with YES without any work

    inds = vector<int>();
    for (int i = 0; i < Q; i++) {
        // collect all queries for current blocck
        inds.push_back(v[i].second);
        // process current block
        if (i + 1 == Q or v[i].first != v[i+1].first) {
            // add left (smaller indexed) edges until the first edge of current block
            // break whenever we detect a cycle
            while (not got_cycle and e_left_next < v[i].first * B) {
                int status = check(E[0][e_left_next], E[1][e_left_next]);
                if (status == -1) {
                    got_cycle = true;
                    break;
                }
                merge(E[0][e_left_next], E[1][e_left_next]);
                e_left_next++;
            }
            // if cycle, just answer all block's queries with YES
            if (got_cycle) {
                for (int j = 0; j < (int)inds.size(); j++) {
                    int ind = inds[j];
                    res[ind] = 1;
                }
            }
            // otherwise solve for the queries within current block
            else {
                solve_for_inds(e_left_next);
            }
            // clear "current block"
            inds = vector<int>();
        }
    }
}


int main()
{
    while (cin >> N >> M >> Q) {
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &E[0][i], &E[1][i]);
            E[0][i]--;
            E[1][i]--;
        }
        for (int i = 0; i < Q; i++) {
            scanf("%d %d", &queries[0][i], &queries[1][i]);
            queries[0][i]--;
            queries[1][i]--;
        }
        solve();
        for (int i = 0; i < Q; i++) {
            if (res[i]) printf("YES\n");
            else printf("NO\n");
        }
    }
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:218:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &E[0][i], &E[1][i]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:223:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &queries[0][i], &queries[1][i]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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