Submission #973423

#	Time	Username	Problem	Language	Result	Execution time	Memory
973423		fatman87878	Joker (BOI20_joker)	C++17	100 / 100	240 ms	17848 KiB

Joker

/*
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(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+1);)++t,query(t,t);
    dp[mid]=t;
    roll_back(chkpt1);
    query(mid,mid);
    t=max(tl,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|1),-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 (stderr)

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: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29