Submission #944523

#	Time	Username	Problem	Language	Result	Execution time	Memory
944523		sofiefu	Joker (BOI20_joker)	C++17	0 / 100	315 ms	262144 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vo vector
#define pb push_back
#define se second
#define fi first
#define sz(x) x.size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define umap unordered_map
#define uset unordered_set

#define rep(i, a, b) for(ll i=(a); i<b; i++)
#define pr1(x) cerr << #x << '=' << x << ' ';
//for google contests
#define all(v) v.begin(), v.end()
#define repd(i, a, b) for(ll i=(b-1); i >= a; i--)
void _pr(signed x) {cerr << x;}
void _pr(long long x) {cerr << x;}
void _pr(unsigned long long x) {cerr << x;}
void _pr(double x) {cerr << x;}
void _pr(char x) {cerr << '\'' << x << '\'';}
void _pr(const char* x) {cerr << x;}
void _pr(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void _pr(const pair<T, V> &x);
template<typename T, typename V> void _pr(const pair<T, V> &x) {cerr << "\e[95m" << "[ "; _pr(x.first); cerr << ", "; _pr(x.second); cerr << "\e[95m" << ']';}
template<typename T> void _pr(const T &x) {int F=0; cerr << '{'; for(auto &i: x) cerr << (F++ ? ", " : ""), _pr(i); cerr << "\e[91m" << '}';}
template <typename T, typename... V> void _pr(T t, V... v) {_pr(t); if(sizeof...(v)) cerr << ", "; _pr(v...);}
#define pr(x...) cerr << "\e[91m" << __func__ << ':' << __LINE__ << " [" << #x << "] = ["; _pr(x); cerr << "\e[91m" << ']' << "\033[0m"  << endl;

//go for outline with ;, then details
ll const inf = LLONG_MAX, mxn = 2e5+4;
int n, m, q, B = sqrt(2e5), ans[mxn];
vo<vi> adj(mxn);
vo<pii> edges;

struct DSU{
    vi par, rnk, color;
    vo<array<int, 5>> bipartite = {{1, 0, 0, 0, 0}, {1, 0, 0, 0, 0}};
    vo<pii> st;
    DSU(int n): par(n), rnk(n), color(n, 0){
        rep(i, 0, n) par[i] = i;
    }

    int findpar(int v){
        if(v==par[v]) return v;
        return findpar(par[v]);
    }

    void unite(int a, int b){
        if(!bipartite.back()[0]){
            bipartite.pb({0, a, b, color[a], color[b]});
        }
        else{
            if(color[a] == color[b] && color[a] != 0){
                bipartite.pb({0, a, b, color[a], color[b]});
            }
            else{
                bipartite.pb({1, a, b, color[a], color[b]});
                if(color[a]) color[b] = color[a]*-1;
                else if(color[b]) color[a] = color[b]*-1;
                else {
                    color[a] = 1, color[b] = -1;
                }
            }
        }

        // pr("merge", a, b, color)
        a = findpar(a), b = findpar(b);

        if(rnk[b] > rnk[a]) swap(a, b);
        st.pb({a, rnk[a]});
        st.pb({b, rnk[b]});
        par[b] = a;
        if(rnk[a] == rnk[b]) rnk[a]++;

    }

    void rollback(){
        rep(i, 0, 2){
            pii v = st.back();
            par[v.fi] = v.fi; rnk[v.fi] = v.se;
            st.pop_back();
        }
        auto [prev, a, b, c1, c2] = bipartite.back();
        color[a] = c1, color[b] = c2;
        bipartite.pop_back();
        // pr("rollback", color)
    }
};

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>q;
    vo<set<array<int, 3>>> block(m/B+1); //r l

    rep(i, 0, m){
        int a, b; cin>>a>>b; a--, --b;
        adj[a].pb(b), adj[b].pb(a);
        edges.pb({a, b});
    }

    rep(i, 0, q){
        int l, r; cin>>l>>r; l--, --r;
        block[l/B].insert({r, l, i});
    }
    
    DSU g(n);
    int p1 = 0;
    // pr(block)
    rep(i, 0, sz(block)){
        if(!sz(block[i])) continue;
        if(i*B > m) break;
        int nexp1 = min(m, i*B), p2 = m;
        // pr(p1, nexp1)
        rep(u, p1, nexp1) g.unite(edges[u].fi, edges[u].se);
        p1 = nexp1;

        for(auto [r, l, queryind]: block[i]){
            // pr(l, r, queryind)
            if(r < p2){
                repd(u, r+1, m){
                    // pr(r+1, m, edges[u])
                    g.unite(edges[u].fi, edges[u].se);
                    p2 = r+1;
                }
            }
            else{
                rep(u, p2, r+1){
                    g.rollback();
                    p2 = r+1; //weird
                }
            }
            rep(u, p1, l){
                // pr(u, edges[u])
                g.unite(edges[u].fi, edges[u].se);
            }
            //check bipartit
            // pr(g.bipartite.back())
            // pr(g.color)
            ans[queryind] = !g.bipartite.back()[0];
            rep(u, p1, l){
                g.rollback();
            }
        }
        rep(u, p2, m) g.rollback(); //from the right
    }

    vo<string> ret = {"NO", "YES"};
    rep(i, 0, q) cout << ret[ans[i]] << "\n";

}

/*
4 4 3
1 2
2 3
3 1
1 4
1 2
4 4 
2 3

6 8 1
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8

*/

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:15:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::set<std::array<long long int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i, a, b) for(ll i=(a); i<b; i++)
      |                                     ^
Joker.cpp:113:5: note: in expansion of macro 'rep'
  113 |     rep(i, 0, sz(block)){
      |     ^~~

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