Submission #944388

#	Time	Username	Problem	Language	Result	Execution time	Memory
944388		sofiefu	Joker (BOI20_joker)	C++14	0 / 100	144 ms	41656 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, bipartite = {1, 1};
    vo<pii> st;
    DSU(int n): par(n), rnk(n), color(n){
        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()){
            bipartite.pb(0);
        }
        else{
            if(color[a] == color[b] && color[a] != 0){
                bipartite.pb(0);
            }
            else{
                if(color[a]) color[b] = color[a]*=-1;
                else if(color[b]) color[a] = color[b]*=-1;
                else {
                    color[a] = 1, color[b] = -1;
                }
                bipartite.pb(1);
            }
        }
 
        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();
        }
        bipartite.pop_back();
    }
};
 
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>q;
    vo<set<array<int, 3>>> block(B); //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 prev = 0, p1 = 0, p2 = m;
    rep(i, 0, sz(block)){
        if(!sz(block[i])) continue;
        int nexp1 = min(m, i*B);
        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)c
            if(r < p2){
                repd(u, r+1, m){
                    g.unite(edges[u].fi, edges[u].se);
                    p2 = r+1;
                }
            }
            else{
                rep(u, p2, r){
                    // pr(p2, r)
                    g.rollback();
                    p2 = r;
                }
            }
            rep(u, nexp1, l){
                g.unite(edges[u].fi, edges[u].se);
            }
            //check bipartit
            if(g.bipartite.back()) ans[queryind] = 0;
            else ans[queryind] = 1;
            rep(u, nexp1, l){
                // pr(g.st)
                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 5
1 2
2 3
3 1
1 4
4 4 
1 1
1 2
2 3
4 4
*/

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:107:5: note: in expansion of macro 'rep'
  107 |     rep(i, 0, sz(block)){
      |     ^~~
Joker.cpp:113:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |         for(auto [r, l, queryind]: block[i]){
      |                  ^
Joker.cpp:106:9: warning: unused variable 'prev' [-Wunused-variable]
  106 |     int prev = 0, p1 = 0, p2 = m;
      |         ^~~~

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