oj.uz

답안 #678734

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678734 2023-01-06T13:04:12 Z elkernos Joker (BOI20_joker) C++17
25 / 100
 342 ms 12536 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) {
        if (i == m) {
            return;
        }
        uf.join(edges[i].first, edges[i].second + n);
        uf.join(edges[i].first + n, edges[i].second);
    };
    auto same = [&](int i) {
        if (i == m) {
            return false;
        }
        return uf.find(edges[i].first) == uf.find(edges[i].first + n);
    };
    function<void(int, int, int, int)> rek = [&](int l, int r, int a, int b) {
        int mid = (l + r) / 2;
        int t1 = uf.time();
        for (int i = l; i < mid; i++) {
            lacz(i);
            if (same(i)) {
                last[mid] = m;
                break;
            }
        }
        int t2 = uf.time();
        for (int i = b; i >= max(mid, a); i--) {
            lacz(i);
            if (same(i)) {
                last[mid] = i;
                break;
            }
        }
        uf.rollback(t2);
        if (mid < r) {
            lacz(mid);
            rek(mid + 1, r, max(mid + 1, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 219 ms 7700 KB Output is correct
4 Correct 208 ms 12536 KB Output is correct
5 Correct 175 ms 12352 KB Output is correct
6 Correct 152 ms 7628 KB Output is correct
7 Correct 165 ms 7640 KB Output is correct
8 Correct 194 ms 5840 KB Output is correct
9 Correct 212 ms 7620 KB Output is correct
10 Correct 342 ms 12500 KB Output is correct
11 Correct 219 ms 7588 KB Output is correct
12 Correct 318 ms 12372 KB Output is correct
13 Correct 198 ms 4188 KB Output is correct
14 Correct 187 ms 5648 KB Output is correct
15 Correct 267 ms 7904 KB Output is correct
16 Correct 340 ms 12508 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -