Submission #1161523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161523		son2008	Joker (BOI20_joker)	C++20	0 / 100	333 ms	20456 KiB

Joker

#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<ll,ii>
#define iiii pair<ii,ii>
#define base 29
#define eps 1e-8
int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=2e5+5,maxm=1e4+5,maxq=1e5+5;
const int mod=1e9+7;
ii edge[maxn],par[maxn];
int f[maxn];
int rk[maxn],n,m,q;
struct node
{
    int a,x,b,y,c,i;
};
stack<node>st;
bool bipartiteness=true,nho[maxn];
ii acs(int u)
{
    if(u!=par[u].fi)
    {
        int parity=par[u].se;
        par[u]=acs(par[u].fi);
        par[u].se^=parity;
    }
    return par[u];
}
bool join(int u,int v,int i)
{
    ii pa=acs(u),pb=acs(v);
    int a=pa.fi,x=pa.se;
    int b=pb.fi,y=pb.se;
    if(a==b)
    {
        if(x==y)
        {
            st.push({a,rk[a],b,rk[b],bipartiteness,i});
            bipartiteness=false;
            return true;
        }
        return false;
    }
    if(rk[a]>rk[b])swap(a,b);
    st.push({a,rk[a],b,rk[b],bipartiteness,i});
    par[a]={b,x^y^1};
    if(rk[b]==rk[a])rk[b]++;
    return true;
}
void rollback()
{
    node t=st.top();
    st.pop();
    int a=t.a,b=t.b,x=t.x,y=t.y,c=t.c;
    par[a]={a,0};
    par[b]={b,0};
    rk[a]=x;
    rk[b]=y;
    bipartiteness=c;
}
void init()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        par[i]={i,0};
    }
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i].fi>>edge[i].se;
    }
}
void dnc(int l1,int l2,int r1,int r2)
{
    if(l1>l2)return;
    int mid=(l1+l2)/2;
   // cout<<l1<<" "<<l2<<" "<<mid<<'\n';
   /* if(mid==6)
    {
        cout<<bipartiteness<<'\n';
        while(!st.empty())
        {
            node tmp=st.top();
            cout<<tmp.i<<'\n';
            st.pop();
        }
        cout<<'\n';
        for(int i=1;i<=n;i++)
        {
            cout<<acs(i).fi<<" ";
        }
        cout<<'\n';
    }*/
    for(int i=l1;i<mid;i++)
    {
        nho[i]=join(edge[i].fi,edge[i].se,i);
    }
    f[mid]=-1;
  //  cout<<mid<<":"<<bipartiteness<<'\n';
    for(int i=r2;i>=max(r1,mid+1);i--)
    {
        if(!bipartiteness)
        {
            f[mid]=i;
            break;
        }
//cout<<100<<" "<<i<<'\n';
        nho[i]=join(edge[i].fi,edge[i].se,i);
    }
    int x=0;
    if(f[mid]==-1)f[mid]=mid-1,x=max(r1,mid+1);
    else x=f[mid]+1;
   // cout<<f[mid]<<":"<<bipartiteness<<'\n';
    //if(mid==6)exit(0);
    for(int i=x;i<=r2;i++)
    {
        if(nho[i])rollback();
    }
    for(int i=mid-1;i>=l1;i--)
    {
        if(nho[i])rollback();
    }
    for(int i=x;i<=r2;i++)
    {
      //  cout<<mid<<" "<<i<<'\n';

        nho[i]=join(edge[i].fi,edge[i].se,i);
    }
   // cout<<l1<<" "<<l2<<" "<<f[mid]+1<<":"<<r2<<" "<<bipartiteness<<'\n';
    dnc(l1,mid-1,r1,f[mid]);
    for(int i=r2;i>=x;i--)if(nho[i])rollback();
    for(int i=l1;i<=mid;i++)
    {
        nho[i]=join(edge[i].fi,edge[i].se,i);
    }
    dnc(mid+1,l2,f[mid],r2);
    for(int i=mid;i>=l1;i--)if(nho[i])rollback();
}
void process()
{
    dnc(1,m,1,m);
    /*for(int i=1;i<=m;i++)
    {
        cout<<f[i]<<" ";
    }
    cout<<'\n';*/
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        if(f[l]>=r)
        {
            cout<<"YES"<<'\n';
        }
        else
            cout<<"NO"<<'\n';
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    init();
    process();
    cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}

Compilation message (stderr)

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

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