Submission #925801

#	Time	Username	Problem	Language	Result	Execution time	Memory
925801		vjudge1	Joker (BOI20_joker)	C++17	39 / 100	2024 ms	28152 KiB

Joker

/*
no more temmy :(
*/

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
// #include<icecream.hpp>
// using namespace icecream;
#define ll long long
#define int ll
#define ld long double
#define y1 cheza
// mt19937 rng(1983413);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=2e5+100;
const int M=1e6;
const int B=317;
const int mod=998244353;
const int INF=1e18;
const int lg=64;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-9;
int n,m,q;
vector<pair<int,int>>g[N];
int a[N];
int lx,rx;
int dfs(int x){

    for(auto [i,w]:g[x]){
        if(lx<=w&&w<=rx)continue;
        if(a[i]==-1){
            a[i]=a[x]^1;
            if(dfs(i)){
                return 1;
            }
        }
        else{
            if(a[i]==a[x]){
                return 1;
            }
        }
    }
    return 0;

}
bool check(){
    for(int i=1;i<=n;i++){
        a[i]=-1;
    }
    for(int i=1;i<=n;i++){
        if(a[i]==-1){
            if(dfs(i)){
                return 1;
            }
        }
    }
    return 0;
}
void solve1(){
    for(;q--;){
        cin>>lx>>rx;
        for(int i=1;i<=n;i++){
            a[i]=-1;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(a[i]==-1){
                if(dfs(i)){
                    ans=1;
                    break;
                }
            }
        }
        if(ans){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }


    }
}
vector<pair<int,int>>f[N];
bitset<N> ans;
void test(){
    cin>>n>>m>>q;
    for(int i=1,x,y;i<=m;i++){
        cin>>x>>y;
        g[x].push_back({y,i});
        g[y].push_back({x,i});
    }
    if(n<=2000&&m<=2000&&q<=2000){
        solve1();
        return;
    }
    for(int i=1;i<=q;i++){
        cin>>lx>>rx;
        f[lx].push_back({rx,i});
    }
    for(int i=1;i<=min(n,200ll);i++){
        sort(f[i].begin(),f[i].end());
        int l=0;
        int r=f[i].size()-1;
        while(l<=r){
            int mid=(l+r)>>1ll;
            lx=i;
            rx=f[i][mid].first;
            if(check()){
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        l--;
        for(int j=0;j<=l;j++){
            ans[f[i][j].second]=1;
        }
    }
    for(int i=1;i<=q;i++){
        if(ans[i]){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }


    
}
/*

*/  
 
signed main(){
    // ic.prefix("debug->| ");
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    long long t2=1;
    //  cin>>t2;
    for(int i=1;i<=t2;i++){
        test();
    }
    
    return 0;
 
}

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