Submission #877335

#	Time	Username	Problem	Language	Result	Execution time	Memory
877335		damwuan	Joker (BOI20_joker)	C++17	0 / 100	89 ms	6596 KiB

Joker

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+69;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
int n,m,q,par[maxn],col[maxn];
pii E[maxn];
int qr[maxn];
vector<pair<int,pii>> save;
pii Find(int u)
{
    int c=0;
    while (par[u]>0)
    {
        c^=col[u];
        u=par[u];
    }
    return {u,c};
}
bool Union(int u,int v)
{
    auto x=Find(u);
    u=x.fi;
    int cu=x.se;
    auto y=Find(v);
    v=y.fi;
    int cv=y.se;
    if (u==v)
    {
        if (cu==cv) return 0;
    }
    else
    {
        if (par[u]>par[v])
        {
            swap(u,v);
        }
        save.pb({v,{par[v],col[v]}});
        if (cu==cv)
        {
            col[v]=1;
        }
        else col[v]=0;
        par[u]+=par[v];
        par[v]=u;
    }
    return 1;
}
void undo(int x)
{
    while(save.size()>x)
    {
        int v=save.back().fi;
        int p=save.back().se.fi;
        int c=save.back().se.se;
        save.pop_back();
        int u=par[v];
        par[v]=p;
        col[v]=c;
        par[u]-=par[v];
    }
}
int dp[maxn];
void Compute(int l,int r,int optl, int optr)
{
    if (l>r) return;
    int snap2=save.size();
    int mid=l+r>>1;
    bool ok=1;
    for1(i,l,mid)
    {
        if (!Union(E[i].fi,E[i].se))
        {
            ok=0;
//            cerr<< "ads\n";
        }
    }
    int snap1=save.size();
    if (ok)
    {
        int opt=optr;
        while (opt>=max(optl,mid+1) &&Union(E[opt].fi,E[opt].se))
        {
            opt--;
        }
        dp[mid]=opt;
        undo(snap1);
        Compute(mid+1,r,dp[mid],optr);
    }
    undo(snap2);
    for2(i,optr,dp[mid]+1) Union(E[i].fi,E[i].se);
    Compute(l,mid-1,optl,dp[mid]);
    undo(snap2);
}
void sol()
{

    cin >> n>> m>> q;
    for1(i,1,n) par[i]=-1;
    for1(i,1,m)
    {
        cin >> E[i].fi>> E[i].se;
        dp[i]=m+1;
    }
    Compute(1,m,1,m);
//    for1(i,1,m) cerr<< dp[i]<<' ';
    while (q--)
    {
        int l,r;cin>>l>>r;
        if (dp[l-1]>r )
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }



}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("GROUPDIV.inp","r",stdin);
//    freopen("GROUPDIV.out","w",stdout);

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

/*
6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6


*/

Compilation message (stderr)

Joker.cpp: In function 'void undo(int)':
Joker.cpp:72:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |     while(save.size()>x)
      |           ~~~~~~~~~~~^~
Joker.cpp: In function 'void Compute(int, int, int, int)':
Joker.cpp:89:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |     int mid=l+r>>1;
      |             ~^~

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