Submission #1125628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125628		luvna	Joker (BOI20_joker)	C++20	100 / 100	330 ms	15516 KiB

Joker

#include<bits/stdc++.h>

#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}

typedef long long ll;
typedef long double ld;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

const int N = 5e5 + 15;

int n, m, q;
pii edges[N];

struct DSU{
    int n, odd_cycle;
    vector<int> par, siz, dist;
    stack<pair<int &, int>> st;

    DSU(int n) : n(n), par(n + 15, 0), siz(n + 15, 0), dist(n + 15, 0) {
        for(int i = 1; i <= n; i++) par[i] = i, siz[i] = 1;
        odd_cycle = 0;
    }

    int asc(int u){
        return par[u] == u ? u : asc(par[u]);
    }

    int dist_from_root(int u){
        return par[u] == u ? 0 : dist[u] ^ dist_from_root(par[u]);
    }

    void join(int u, int v){
        int total = dist_from_root(u) ^ dist_from_root(v) ^ 1;
        u = asc(u), v = asc(v);
        if(u == v){
            st.push({odd_cycle, odd_cycle});
            odd_cycle |= total;
            return;
        }
        if(siz[v] > siz[u]) swap(u,v);
        st.push({par[v], par[v]});
        st.push({siz[u], siz[u]});
        st.push({dist[v], dist[v]});
        par[v] = u;
        siz[u] += siz[v];
        dist[v] = total;
    }

    int snap() {return sz(st);}

    void rollback(int snapshot){
        assert(snap() >= snapshot);
        while(snap() > snapshot){
            st.top().fi = st.top().se;
            st.pop();
        }
    }
};

int dp[N];

void dnc(int l, int r, int optL, int optR, DSU &dsu){
    if(l > r || optL > optR) return;

    int snap_right  = dsu.snap();

    int mid = (l+r) >> 1;

    for(int i = mid+1; i <= r; i++){
        dsu.join(edges[i].fi, edges[i].se);
    }

    int snap_find = dsu.snap();

    int opt = mid+1;

    for(int i = optL; i <= min(mid,optR) ; i++){
        if(dsu.odd_cycle){
            opt = i;
            break;
        }
        dsu.join(edges[i].fi, edges[i].se);
    }

    dp[mid] = opt;

    dsu.rollback(snap_find);

    dsu.join(edges[mid].fi, edges[mid].se);
    dnc(l,mid-1,optL,opt, dsu);

    dsu.rollback(snap_right);

    for(int i = optL; i < opt; i++) dsu.join(edges[i].fi, edges[i].se);

    dnc(mid+1,r,opt,optR, dsu);
}

void solve(){
    cin >> n >> m >> q;

    for(int i = 1; i <= m; i++) cin >> edges[i].fi >> edges[i].se;

    DSU dsu(n);

    for(int i = 1; i <= m; i++) dp[i] = m+1;

    dnc(1,m,1,m,dsu);

    //for(int i = 1; i <= m; i++) cout << dbg(i) << dbg(dp[i]) << endl;

    while(q--){
        int l, r; cin >> l >> r;
        cout << (dp[r] <= l ? "YES" : "NO") << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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