oj.uz

Submission #877332

# Submission time Handle Problem Language Result Execution time Memory
877332 2023-11-23T06:41:18 Z damwuan Joker (BOI20_joker) C++17
0 / 100
 2000 ms 6592 KB 


#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)
{
    if (par[u]<0) return {u,c^col[u]};
    else
    {
        return Find(par[u],c^col[u]);
    }
}
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;
        }
        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;
//    cerr<< "CHECKING "<<mid<<'\n';
//    cerr<< l<<' '<<r<<' '<<snap2<<" snap2\n";
    bool ok=1;
    for1(i,l,mid)
    {
        if (!Union(E[i].fi,E[i].se))
        {
            ok=0;
        }
//        cerr<< i<<'\n';
    }
    int snap1=save.size();
//    if (!ok) cout << "SKIP "<<mid<<'\n';
//    cerr<< l<<' '<<r<<' '<<snap1<<" snap1\n";
//    if (mid==3) cerr<< optl<<' '<<optr<<'\n';
    if (ok)
    {
        int opt=optr;
        while (opt>=max(optl,mid+1) &&Union(E[opt].fi,E[opt].se))
        {
//            cerr<< opt<<'\n';
            opt--;
        }
        dp[mid]=opt;
//        cerr<< l<<' '<<r<<' '<<snap1<<" roll1\n";
        undo(snap1);
        Compute(mid+1,r,dp[mid],optr);
    }
//    cerr<< l<<' '<<r<<' '<<snap2<<" roll2\n";
    undo(snap2);
    for2(i,optr,dp[mid]+1) Union(E[i].fi,E[i].se);
    Compute(l,mid-1,optl,dp[mid]);
//    cerr<< l<<' '<<r<<' '<<snap2<<" roll2\n";
    undo(snap2);
//    cerr<< "END "<<mid<<'\n';
}
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) cout << dp[i]<<' ';
    while (q--)
    {
        int l,r;cin>>l>>r;
        if (dp[l-1]>r )
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
//par[1]=par[2]=par[3]=-1;
//cerr<< Union(1,2)<<' '<<Union(2,3)<<' '<<Union(1,3);




}
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();
    }
}

Compilation message

Joker.cpp: In function 'void undo(int)':
Joker.cpp:69: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]
   69 |     while(save.size()>x)
      |           ~~~~~~~~~~~^~
Joker.cpp: In function 'void Compute(int, int, int, int)':
Joker.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Execution timed out 2090 ms 4444 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Execution timed out 2090 ms 4444 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 89 ms 6592 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Execution timed out 2090 ms 4444 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Execution timed out 2090 ms 4444 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Execution timed out 2090 ms 4444 KB Time limit exceeded
5 Halted 0 ms 0 KB -