oj.uz

Submission #678718

# Submission time Handle Problem Language Result Execution time Memory
678718 2023-01-06T12:51:30 Z elkernos Joker (BOI20_joker) C++17
0 / 100
 1 ms 212 KB 
// while (clock()<=69*CLOCKS_PER_SEC)
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("O3")
// #pragma GCC target ("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                    \
    sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
    {
sim > struct rge {
    c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
    ~debug()
    {
        cerr << endl;
    }
    eni(!=) cerr << boolalpha << i;
    ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
    ris << "" << d.first << " --> " << d.second << "";
}
sim dor(rge<c> d)
{
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
    sim dor(const c &)
    {
        ris;
    }
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#ifdef XOX
#warning Times may differ!!!
#endif

#define endl '\n'
#define pb emplace_back
#define vt vector
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int nax = 1000 * 1007, mod = 1e9 + 7;

struct RollbackUF {
    vt<int> e;
    vt<pii> st;
    RollbackUF(int n) : e(n, -1) {}
    int size(int x) { return -e[find(x)]; }
    int find(int x) { return e[x] < 0 ? x : find(e[x]); }
    int time() { return sz(st); }
    void rollback(int t)
    {
        for (int i = time(); i-- > t;)
            e[st[i].first] = st[i].second;
        st.resize(t);
    }
    bool join(int a, int b)
    {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (e[a] > e[b]) swap(a, b);
        st.pb(a, e[a]);
        st.pb(b, e[b]);
        e[a] += e[b];
        e[b] = a;
        return true;
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m >> q;
    vt<pii> edges(m);
    for (auto &[a, b] : edges) {
        cin >> a >> b;
    }
    RollbackUF uf(2 * n + 12);
    vt<int> last(m);
    auto lacz = [&](int i) {
        uf.join(edges[i].first, edges[i].second + n);
        uf.join(edges[i].first + n, edges[i].second);
    };
    auto same = [&](int i) {
        return uf.find(edges[i].first) == uf.find(edges[i].first + n) || uf.find(edges[i].second) == uf.find(edges[i].second + n);
    };
    function<void(int, int, int, int)> rek = [&](int l, int r, int a, int b) {
        // if (a == b) {
        //     for (int i = l; i <= r; i++) {
        //         last[i] = a;
        //     }
        //     return;
        // }
        int mid = (l + r) / 2;
        int t1 = uf.time();
        for (int i = l; i < mid; i++) {
            lacz(i);
        }
        int t2 = uf.time();
        for (int i = b; i >= mid; i--) {
            lacz(i);
            if (same(i)) {
                last[mid] = i;
                break;
            }
        }
        if (!last[mid]) {
            last[mid] = m;
        }
        uf.rollback(t2);
        if (mid < r) {
            lacz(mid);
            rek(mid + 1, r, last[mid], b);
        }
        uf.rollback(t1);
        if (l < mid) {
            int t3 = uf.time();
            for (int i = b; i > last[mid]; i--) {
                lacz(i);
            }
            rek(l, mid - 1, a, last[mid]);
            uf.rollback(t3);
        }
    };
    rek(0, m - 1, 0, m - 1);
    debug() << imie(last);
    while (q--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        cout << (last[a] <= b ? "NO" : "YES") << endl;
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 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 212 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 212 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 212 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 212 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -