Submission #667477

#	Time	Username	Problem	Language	Result	Execution time	Memory
667477		fatemetmhr	Joker (BOI20_joker)	C++17	100 / 100	290 ms	14832 KiB

Joker

// ~ Be Name Khoda ~

// author: Fatemeh :/


#include<bits/stdc++.h>
//#pragma GCC optimize("O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

struct posit{
    bool oddcy;
    int v, u, paru, parv;
    posit(bool od, int vv, int uu, int pv, int pu){
        oddcy = od;
        v = vv;
        u = uu;
        parv = pv;
        paru = pu;
    }
};

vector <posit> av;
bool ty[maxn5], oddcy = false;
int par[maxn5], a[maxn5], b[maxn5], ans[maxn5];

pair<int, int> get_par(int v){
    int x = 0;
    while(par[v] >= 0){
        x ^= ty[v];
        v = par[v];
    }
    return {v, x};
}

inline void add(int i){
    pair<int, int> ver1 = get_par(a[i]), ver2 = get_par(b[i]);
    int v = ver1.fi, u = ver2.fi;
    if(u == v){
        posit cur(oddcy, -1, -1, -1, -1);
        av.pb(cur);
        oddcy |= (ver1.se == ver2.se);
        return;
    }
    if(par[v] < par[u])
        swap(u, v);
    posit cur(oddcy, v, u, par[v], par[u]);
    av.pb(cur);
    if(par[v] == par[u])
        par[u]--;
    par[v] = u;
    ty[v] = (ver1.se ^ ver2.se ^ 1);
    return;
}

inline void undo(){
    posit cur = av.back(); av.pop_back();
    oddcy = cur.oddcy;
    if(cur.u == -1)
        return;
    par[cur.u] = cur.paru;
    par[cur.v] = cur.parv;
    return;
}

void solve(int l, int r, int optl, int optr){
    if(r <= l || optr <= optl || optr <= l)
        return;
    int keepsize = av.size();
    int mid = (l + r) >> 1;
    for(int i = l; i < mid; i++)
        add(i);
    int opt = mid - 1;
    if(oddcy){
        opt = optr - 1;
    }
    else{
        for(int i = optr - 1; i > max(mid, optl); i--){
            add(i);
            if(oddcy){
                opt = i - 1;
                break;
            }
        }
    }
    ans[mid] = opt;
    while(av.size() > keepsize)
        undo();
    for(int i = optr - 1; i > opt; i--)
        add(i);
    solve(l, mid, optl, opt + 1);
    while(av.size() > keepsize)
        undo();
    for(int i = l; i <= mid; i++)
        add(i);
    solve(mid + 1, r, opt, optr);
    while(av.size() > keepsize)
        undo();
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, m, q; cin >> n >> m >> q;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        ans[i] = i - 1;
    }
    memset(par, -1, sizeof par);
    solve(0, m, 0, m);
    for(int i = 0; i < q; i++){
        int l, r; cin >> l >> r;
        l--; r--;
        cout << (ans[l] >= r ? "YES\n" : "NO\n");
    }
}

/*
Why so fast...? 
Hold on...
Hold your breath...
Need anything else?

Nein, Kein Problem...
Das Leben war schon immer so grausam :)
*/

Compilation message (stderr)

Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:102:21: warning: comparison of integer expressions of different signedness: 'std::vector<posit>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |     while(av.size() > keepsize)
      |           ~~~~~~~~~~^~~~~~~~~~
Joker.cpp:107:21: warning: comparison of integer expressions of different signedness: 'std::vector<posit>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |     while(av.size() > keepsize)
      |           ~~~~~~~~~~^~~~~~~~~~
Joker.cpp:112:21: warning: comparison of integer expressions of different signedness: 'std::vector<posit>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |     while(av.size() > keepsize)
      |           ~~~~~~~~~~^~~~~~~~~~

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