oj.uz

Submission #973409

# Submission time Handle Problem Language Result Execution time Memory
973409 2024-05-02T01:16:46 Z fatman87878 Joker (BOI20_joker) C++17
0 / 100
 1 ms 2396 KB 
/*
The middle of adventure, such a perfect place to start
⣿⣿⣿⣿⣿⣿⣿⢿⠟⢿⣿⣿⣿⣿⠿⠛⠛⠿⢿⣿⣿⣿⣿⠛⣿⢿⣿⣿⣿⣿
⣿⣿⣿⡿⢿⣿⣿⣄⠄⣼⣿⡿⠋⠄⠄⠄⠄⠄⠄⠄⠛⣿⣿⠄⢀⣤⣿⣿⣿⣿
⣿⣿⣷⣤⣸⣿⠛⡛⢛⣿⠋⠄⠄⢀⠄⠄⠄⠄⠄⠄⠄⠘⣿⣿⡿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⡿⠁⠄⠁⠈⠄⠄⠄⠄⣿⡀⠄⠄⠄⠄⠄⠄⠄⠓⠸⠏⠄⢹⣿⣿⣿
⣿⣿⣿⡿⠄⠄⠄⠄⠄⠄⠄⢠⠿⠿⢻⣦⣤⣠⠄⠄⠄⠄⠄⠄⠄⠄⠈⠻⣿⣿
⣿⣿⡿⠁⠄⠄⠄⠄⠈⠄⠄⢸⣿⣿⣿⣿⣿⢭⡛⡀⠄⠄⠨⠄⠄⠄⠄⠄⣿⣿
⣿⣿⠁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠻⣧⡀⣈⣿⣿⠟⠄⠄⠠⢇⠄⠄⠄⠄⠄⣿⣿
⣿⡁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⢀⣉⡉⠉⠄⠄⠄⠄⠄⠰⠂⠄⠄⠄⠄⢹⣿
⣿⡇⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⣿⠿⠁⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠘⣿
⣿⣿⣶⣤⣤⣄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⣼⣿
We're not strangers to love
You know the rules, and so do I
A full comitment of what I'm thinking of
You can't get this from any other guy
I just wanna tell you how I'm feeling
Gotta make you, understand
Never gonna give you up
Never gonna let you down
Never gonna round around and desert you
Never gonna make you cry
Never gonna say goodbye
Never gonna tell a lie and hurt you
duh duh duh duh duh`
*/
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=2e5+5;

I n,m,q,oddcir,dp[maxN],dsu[maxN<<1];

pii edges[maxN];

vector<pii> opt;

inline I find(I pos){
    return dsu[pos]<0?pos:find(dsu[pos]);
}

inline void join(I a,I b){
    I fa=find(a),fb=find(b);
    if(fa==fb)return;
    if(dsu[fa]<dsu[fb])swap(fa,fb),swap(a,b);
    opt.emplace_back(fa,dsu[fa]),opt.emplace_back(fb,dsu[fb]);
    dsu[fb]+=dsu[fa],dsu[fa]=fb;
    if(find(2*n+1-a)==fb||find(2*n+1-b)==fb)opt.emplace_back(-1,oddcir),oddcir++;
}

inline void add(I a,I b){
    join(a,2*n+1-b),join(b,2*n+1-a);
}

inline void query(I l,I r){
    for(;l<=r;l++)add(edges[l] F,edges[l] S);
}

inline void roll_back(I val){
    for(;opt.size()>val;opt.pop_back()){
        if(opt.back() F>0)dsu[opt.back() F]=opt.back() S;
        else oddcir--;
    }
}

void fun_and_jizz(I tl,I tr,I l,I r){
    if(tl>tr||l>r)return;
    I mid=l+r>>1,t=tl-1,chkpt0,chkpt1;
    chkpt0=opt.size();
    query(mid+1,r);
    for(chkpt1=opt.size();!oddcir&&t<min(tr,mid);)++t,query(t,t);
    dp[mid]=t;
    roll_back(chkpt1);
    query(mid,mid);
    t=max(1,t);
    fun_and_jizz(tl,t,l,mid-1);
    roll_back(chkpt0);
    query(tl,t-1);
    fun_and_jizz(t,tr,mid+1,r);
    roll_back(chkpt0);
}

I main(){
    IOS
    cin>>n>>m>>q;
    fill(dsu,dsu+(n<<1)+2,-1);
    rep(i,1,m+1)cin>>edges[i] F>>edges[i] S;
    fun_and_jizz(1,m,1,m);
    for(I a,b;q--;){
        cin>>a>>b;
        cout<<(a>=dp[b]?"YES\n":"NO\n");
    }
}

Compilation message

Joker.cpp: In function 'void roll_back(int)':
Joker.cpp:74:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     for(;opt.size()>val;opt.pop_back()){
      |          ~~~~~~~~~~^~~~
Joker.cpp: In function 'void fun_and_jizz(int, int, int, int)':
Joker.cpp:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     I mid=l+r>>1,t=tl-1,chkpt0,chkpt1;
      |           ~^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -