oj.uz

Submission #676806

# Submission time Handle Problem Language Result Execution time Memory
676806 2023-01-01T08:28:38 Z dooompy Joker (BOI20_joker) C++17
25 / 100
 190 ms 12532 KB 
#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 = m + 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

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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 128 ms 5708 KB Output is correct
4 Correct 176 ms 12520 KB Output is correct
5 Correct 145 ms 12532 KB Output is correct
6 Correct 105 ms 9868 KB Output is correct
7 Correct 112 ms 9812 KB Output is correct
8 Correct 118 ms 8204 KB Output is correct
9 Correct 161 ms 9044 KB Output is correct
10 Correct 176 ms 10692 KB Output is correct
11 Correct 141 ms 9540 KB Output is correct
12 Correct 147 ms 10940 KB Output is correct
13 Correct 122 ms 7444 KB Output is correct
14 Correct 121 ms 8608 KB Output is correct
15 Correct 175 ms 10176 KB Output is correct
16 Correct 190 ms 11140 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -