Submission #1169832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169832		InvMOD	Joker (BOI20_joker)	C++20	100 / 100	236 ms	15492 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REV(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;


struct DSU{
    vector<pair<int,int>> par; vector<int> sz;

    stack<pair<int&, int>> st; int good;

    void init(int n){
        par.resize(n + 1);
        sz.resize(n + 1);

        FOR(i, 1, n){
            par[i] = make_pair(i, 0);
            sz[i] = 1;
        }
        good = 0;
    }

    pair<int,int> asc(int x){
        if(x == par[x].fi) return par[x];

        pair<int,int> v = asc(par[x].fi);
        v.se ^= par[x].se;
        return v;
    }

    void join(int a, int b){
        pair<int,int> u = asc(a);
        pair<int,int> v = asc(b);

        if(u.fi == v.fi){
            if(u.se ^ v.se ^ 1){
                st.push({good, good});
                good = good | (u.se ^ v.se ^ 1);
            }
        }
        else{
            if(sz[u.fi] < sz[v.fi]) swap(u, v);

            st.push({sz[u.fi], sz[u.fi]});
            st.push({par[v.fi].fi, par[v.fi].fi});
            st.push({par[v.fi].se, par[v.fi].se});

            par[v.fi] = make_pair(u.fi, u.se ^ 1 ^ v.se);
            sz[u.fi] += sz[v.fi];
        }
    }

    bool isGood(){
        return good;
    }

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

    void rollback(int snipe){
        while(sz(st) > snipe){
            st.top().fi = st.top().se;
            st.pop();
        }
    }
};

int n, m, q, dp[N];

pair<int,int> E[N]; DSU dsu;

void Dnc(int l, int r, int optL, int optR){
    if(l > r) return;

    int mid = l+r>>1, snipe = dsu.snap();

    for(int p = l; p < mid; p++){
        dsu.join(E[p].fi, E[p].se);
    }
    int snipe2 = dsu.snap();

    int best = -1;
    if(dsu.isGood()){
        best = optR;
    }
    else{
        for(int pos = optR - 1; pos >= mid; pos--){
            dsu.join(E[pos].fi, E[pos].se);
            if(dsu.isGood()){
                best = pos;
                break;
            }
        }
    }
    dp[mid] = best;
    dsu.rollback(snipe2);
    dsu.join(E[mid].fi, E[mid].se);

    Dnc(mid + 1, r, best, optR);

    dsu.rollback(snipe);
    for(int pos = optR - 1; pos >= best; pos--){
        dsu.join(E[pos].fi, E[pos].se);
    }

    Dnc(l, mid - 1, optL, best);
}

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

    FOR(i, 1, m) cin >> E[i].fi >> E[i].se;

    dsu.init(n);

    FOR(i, 1, m){
        dsu.join(E[i].fi, E[i].se);
    }

    if(!dsu.isGood()){
        FOR(i, 1, q){
            int l,r; cin >> l >> r;
            cout << "NO\n";
        }
        return;
    }
    dsu.rollback(0);

    Dnc(1, m, 1, m + 1);

    while(q--){
        int l,r; cin >> l >> r;

        cout << (dp[l] > r ? "YES" : "NO") << "\n";
    }
}

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

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

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

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:171:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |         freopen(name".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