Submission #676808

#	Time	Username	Problem	Language	Result	Execution time	Memory
676808		dooompy	Joker (BOI20_joker)	C++17	100 / 100	186 ms	14224 KiB

Joker

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

pair<int, int> roads[200005];


struct dsu {
    vector<pair<int, int>> par;
    vector<int> rnk;
    vector<array<int, 4>> history;

    void init(int n) {
        par.resize(n + 1); rnk.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            par[i] = {i, 0}, rnk[i] = 1;
        }
    }

    pair<int, int> findset(int i) {
        if (i == par[i].first) return par[i];
        int parity = par[i].second;
        pair<int, int> temp =  findset(par[i].first);
        temp.second ^= parity;

        return temp;
    }

    bool onion(int a, int b) {
        auto tempa = findset(a), tempb = findset(b);

        if (tempa.first == tempb.first) {
            if (tempa.second == tempb.second) return false;

            return true;
        }

        a = tempa.first, b = tempb.first;

        if (rnk[a] > rnk[b]) swap(a, b);
        history.push_back({a, rnk[a], b, rnk[b]});

        par[a] = {b, tempa.second^tempb.second^1};

        if (rnk[a] == rnk[b]) rnk[b]++;
        return true;
    }

    void rollback(int idx) {
        while (history.size() > idx) {
            auto [a, rnka, b, rnkb] = history.back();
            history.pop_back();

            rnk[a] = rnka, rnk[b] = rnkb;

            par[a] = {a, 0};
        }
    }
};

dsu ds;
int n, m, q;
int lst[200005];

void dnc(int l, int r, int ql, int qr) {
    if (r < l) return;

    int mid = (l + r) / 2;

    int res = -1;

    int b1 = ds.history.size();
    for (int i = l; i < mid; i++) {
        int id = ds.onion(roads[i].first, roads[i].second);

        if (!id) {
            res = qr;
            break;
        }
    }

    int b2 = ds.history.size();
    if (res == -1) {
        for (int i = qr; i > ql; i--) {
            if (i == m + 1) continue;
            if (!ds.onion(roads[i].first, roads[i].second)) {
                res = i; break;
            }
        }

        if (res == -1) res = ql;
    }

    lst[mid] = res;

    if (res == m + 1) {
        for (int i = mid + 1; i <= r; i++) lst[i] = m + 1;
    } else {
        ds.rollback(b2);
        if (!ds.onion(roads[mid].first, roads[mid].second)) {
//            cout << "REACHED" << endl;
            for (int i = mid + 1; i <= r; i++) lst[i] = m + 1;
        } else {
            dnc(mid + 1, r, lst[mid], qr);
        }
    }

    ds.rollback(b1);
    for (int i = lst[mid] + 1; i <= qr; i++) {
        ds.onion(roads[i].first, roads[i].second);
    }

    dnc(l, mid - 1, ql, lst[mid]);
    ds.rollback(b1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        roads[i] = {a, b};
    }

    ds.init(n);

    dnc(1, m, 1, m + 1);

    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;

        if (lst[l] <= r) cout << "NO\n";
        else cout << "YES\n";
    }
}

Compilation message (stderr)

Joker.cpp: In member function 'void dsu::rollback(int)':
Joker.cpp:77:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |         while (history.size() > idx) {
      |                ~~~~~~~~~~~~~~~^~~~~

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