Submission #1110056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110056		AverageAmogusEnjoyer	Joker (BOI20_joker)	C++17	100 / 100	1582 ms	26440 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

constexpr int nax = 200200,block_size = 450;
vector<tuple<int,int,int>> queries[block_size]; // r,l,idx
vector<bool> ans;
int edges[nax][2];
int n,m;
bool pref[nax];
bool suff[nax];
bool pref_suff[nax];

struct dsu_save {
    int x,y,lzx,lzy,szx,szy,parx,pary;
};

struct DSU {
    int lz[nax];
    int par[nax];
    int sz[nax];
    dsu_save stk[nax]; // avoid allocating a lot of memory on heap -- better to allocate initially on stack 
    int T = 0;
    void init() {
        for (int i = 0; i < nax; i++)
            lz[i] = 0, par[i] = i, sz[i] = 1;
    }
    int get(int x,int &cx) {
        while(1) {
            cx ^= lz[x];
            if (x == par[x])
                return x;
            x = par[x];
        }
    }
    bool need_reset = 0;
    bool unite(int x,int y) {
        assert(!need_reset);
        int cx = 0,cy = 0;
        int px = get(x,cx), py = get(y,cy);
        if (sz[px] < sz[py]) 
            swap(px,py), swap(cx,cy);
        stk[T++] = {px,py,lz[px],lz[py],sz[px],sz[py],par[px],par[py]};
        if (cx == cy) {
            if (px == py) {
                need_reset = 1;
                return 1;
            } else {
                lz[py] ^= 1;
                sz[px] += sz[py];
                par[py] = px;
            }
        } else {
            if (px != py) {
                sz[px] += sz[py];
                par[py] = px;
            }
        }
        return 0;
    }
    void rollback(int k) {
        need_reset = 0;
        assert(T >= k);
        while(k--) {
            auto &c = stk[--T];
            lz[c.x] = c.lzx,lz[c.y] = c.lzy,par[c.x] = c.parx,par[c.y] = c.pary,sz[c.x] = c.szx,sz[c.y] = c.szy;
        }
    }
};

DSU dsu; 

bool solve_block(int block) {
    int current_r = m - 1;
    for (int i = max(0,(block - 1) * block_size); i < min(m,block * block_size); i++) {
        if (dsu.unite(edges[i][0],edges[i][1])) {
            for (int B = block; B < block_size; B++) 
                for (auto &[r,l,idx]: queries[B])
                    ans[idx] = 1;
            return 1;
        }
    }
    for (int i = 0; i < queries[block].size(); i++) {
        auto &[r,l,idx] = queries[block][i];
        if (pref[l] || suff[m - r] || pref_suff[min(l,m - r)]) {
            ans[idx] = 1;
            continue;
        }
        while(current_r >= r) {
            if (dsu.unite(edges[current_r][0],edges[current_r][1])) {
                for (int j = i; j < queries[block].size(); j++) {
                    int idx2 = get<2>(queries[block][j]);
                    ans[idx2] = 1;
                }
                dsu.rollback(m - current_r); // potrebbero essere necessari dei +- 1
                return 0;
            }
            current_r--;
        }
        --l;
        int inserted = 0;
        while(l >= block * block_size) {
            // devo inserirlo
            inserted++;
            // cout << "edge index: " << l + 1 << endl;
            if (dsu.unite(edges[l][0],edges[l][1])) {
                ans[idx] = 1;
                break;
            }
            l--;
        }
        dsu.rollback(inserted);
    }
    dsu.rollback(m - current_r - 1);
    return 0;
}

bool res[block_size][block_size];
void precomp() {
    dsu.init();
    for (int block = 0; block < block_size; block++) {
        bool flag = 0;
        int ins = 0;
        for (int other = block_size - 1; other > block && !flag; other--) {
            int l = other * block_size; // questo e' acceso!
            int r = min(m,(other + 1) * block_size);
            --r;
            while(r >= l) {
                ins++;
                if (dsu.unite(edges[r][0],edges[r][1])) {
                    for (int O = other; O > block; O--) 
                        res[block][O] = 1;
                    flag = 1;
                    dsu.rollback(ins);
                    ins = 0;
                    break;
                }
                r--;
            }
        }
        dsu.rollback(ins);
        assert(dsu.T == min(m,block * block_size));
        for (int i = block_size * block; i < (block + 1) * block_size && i < m; i++) {
            if (dsu.unite(edges[i][0],edges[i][1])) {
                for (int BL = block + 1; BL < block_size; BL++)
                    for (int BR = BL + 1; BR < block_size; BR++) 
                        res[BL][BR] = 1;
                dsu.rollback(i + 1);
                assert(dsu.T == 0);
                return;
            }
        }
    } 
    assert(dsu.T == m);
    dsu.rollback(m);   
}

bool FOUND_GLOBAL = 0;

void precomp2() {
    dsu.init();
    int i = 1; 
    while(i <= m && !dsu.unite(edges[i - 1][0],edges[i - 1][1])) i++;
    FOUND_GLOBAL = (i != m + 1);
    if (!FOUND_GLOBAL) {
        dsu.rollback(m);
        return;
    }
    dsu.rollback(i);
    while(i <= m)
        pref[i++] = 1;
    i = 1;
    while(i <= m && !dsu.unite(edges[m - i][0],edges[m - i][1])) i++;
    dsu.rollback(i);
    assert(dsu.T == 0);
    while(i <= m)
        suff[i++] = 1;
    int l = 0, r = m - 1;
    int p = 0;
    bool f = 0;
    while(l < r) {
        p++;
        if (dsu.unite(edges[l][0],edges[l][1])) {
            f = 1;
            break;            
        }
        p++;
        if (dsu.unite(edges[r][0],edges[r][1])) {
            f = 1;
            break;
        }
        l++,r--;
    }
    dsu.rollback(p);
    assert(dsu.T == 0);
    p = (p + 1) / 2;
    while(p <= m)
        pref_suff[p++] = f;

}


vector<bool> trova_cicli(int N, int M, int Q, vector<int> A, vector<int> B, vector<int> L, vector<int> R) {
    n = N, m = M;
    for (int i = 0; i < M; i++)
        edges[i][0] = A[i],edges[i][1] = B[i];
    // precomp(); too slow for now
    precomp2();   
    dsu.init();
    ans.resize(Q);
    if (!FOUND_GLOBAL)
        return ans; 
    for (int i = 0; i < Q; i++) 
        queries[L[i] / block_size].emplace_back(R[i],L[i],i);
    for (int i = 0; i < block_size; i++) 
        sort(queries[i].rbegin(),queries[i].rend());
    for (int i = 0; i < block_size; i++) 
        if (solve_block(i))
            break;
    return ans;
}

int main() {

    int N,M,Q;
    cin >> N >> M >> Q;
    vector<int> A(M),B(M),L(Q),R(Q);
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i];
        --A[i],--B[i];
    }
    for (int i = 0; i < Q; i++) {
        cin >> L[i] >> R[i];
        --L[i];
    }
    auto risposta = trova_cicli(N,M,Q,A,B,L,R);
    for (int i = 0; i < Q; i++) 
        cout << (risposta[i] ? "YES" : "NO") << "\n";

}

Compilation message (stderr)

Joker.cpp: In function 'bool solve_block(int)':
Joker.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < queries[block].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:93:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                 for (int j = i; j < queries[block].size(); j++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~

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