oj.uz

답안 #678731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678731 2023-01-06T13:03:26 Z elkernos Joker (BOI20_joker) C++17
25 / 100
 342 ms 15180 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, 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 0 ms 320 KB Output is correct
4 Incorrect 1 ms 316 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 0 ms 320 KB Output is correct
4 Incorrect 1 ms 316 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 198 ms 11452 KB Output is correct
4 Correct 213 ms 15160 KB Output is correct
5 Correct 175 ms 15052 KB Output is correct
6 Correct 163 ms 11324 KB Output is correct
7 Correct 160 ms 11324 KB Output is correct
8 Correct 178 ms 9160 KB Output is correct
9 Correct 209 ms 10420 KB Output is correct
10 Correct 333 ms 15180 KB Output is correct
11 Correct 223 ms 10824 KB Output is correct
12 Correct 288 ms 15080 KB Output is correct
13 Correct 170 ms 8008 KB Output is correct
14 Correct 183 ms 9668 KB Output is correct
15 Correct 270 ms 11580 KB Output is correct
16 Correct 342 ms 15160 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 0 ms 320 KB Output is correct
4 Incorrect 1 ms 316 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 0 ms 320 KB Output is correct
4 Incorrect 1 ms 316 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 0 ms 320 KB Output is correct
4 Incorrect 1 ms 316 KB Output isn't correct
5 Halted 0 ms 0 KB -