Submission #1181598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181598		12345678	Joker (BOI20_joker)	C++20	100 / 100	174 ms	7344 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, m, q, U[nx], V[nx], dp[nx], f, l, r;

struct DSUrollback
{
    int sz[nx];
    pair<int, int> dsu[nx];
    stack<pair<int, int>> history;
    bool is_bipartite=1;
    pair<int, int> find(int u)
    {
        if (dsu[u].first==u) return dsu[u];
        auto tmp=find(dsu[u].first);
        return {tmp.first, tmp.second^dsu[u].second};
    }
    void unite(int u, int v)
    {
        auto [pu, cu]=find(u);
        auto [pv, cv]=find(v);
        if (pu!=pv)
        {   
            if (sz[pu]<sz[pv]) swap(pu, pv);
            dsu[pv]={pu, cu^cv^1};
            sz[pu]+=sz[pv];
            history.push({pu, pv});
        }
        else if (cu==cv)
        {
            if (is_bipartite) history.push({-1, -1});
            is_bipartite=0;
        }
    }
    void rollback(int state)
    {
        while (history.size()>state)
        {
            auto [u, v]=history.top();
            history.pop();
            if (u==-1)
            {
                is_bipartite=1;
            }
            else
            {
                dsu[v]={v, 0};
                sz[u]-=sz[v];
            }
        }
    }
} d;

void solve(int l, int r, int optr)
{
    if (r<l) return;
    int md=(l+r)/2, opt=optr, state1=d.history.size();
    for (int i=l; i<md; i++) d.unite(U[i], V[i]);
    int state2=d.history.size();
    while (d.is_bipartite) d.unite(U[opt], V[opt]), opt--;
    dp[md]=opt;
    d.rollback(state2);
    d.unite(U[md], V[md]);
    solve(md+1, r, optr);
    d.rollback(state1);
    for (int i=optr; i>opt; i--) d.unite(U[i], V[i]);
    solve(l, md-1, opt);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<=n; i++) d.sz[i]=1, d.dsu[i]={i, 0};
    for (int i=1; i<=m; i++) cin>>U[i]>>V[i], d.unite(U[i], V[i]);
    f=d.is_bipartite;
    d.rollback(0);
    if (!f) solve(1, m, m);
    //for (int i=1; i<=n; i++) cout<<"dp "<<i<<' '<<dp[i]<<'\n';
    while (q--)
    {
        cin>>l>>r;
        if (f) cout<<"NO\n";
        else if (r<=dp[l]) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

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