Submission #992459

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
992459	2024-06-04T13:36:25 Z	Fatonim	Joker (BOI20_joker)	C++17	25 / 100	57 ms	10576 KB

Joker

// "We create our own demons."
#include <bits/stdc++.h>

using namespace std;

#ifdef ONPC
    #include "debug.h"
#else
    #define dbg(...)
#endif

#define int long long
#define ll long long
#define ld long double
#define pi pair<int, int>
// vector
#define sz(a) (int)((a).size())
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxpos(x) (max_element(all(x)) - x.begin())
#define minpos(x) (min_element(all(x)) - x.begin())
#define srt(x) (sort(all(x)))
#define rev(x) (reverse(all(x)))
// bitwise operations
#define cnt_bit(n) __builtin_popcountll(n)
#define low_bit(n) ((n) & (-(n)))
#define bit(n, i) (((n) >> (i)) & 1)
#define set_bit(n, i) ((n) | (1LL << (i)))
#define reset_bit(n, i) ((n) & ~(1LL << (i)))
#define flip_bit(n, i) ((n) ^ (1LL << (i)))
// math
#define sqr(n) ((n) * (n))
#define divup(a, b) (((a) + (b)-1) / (b))
// ostream
#define Fixed(a) cout << fixed << setprecision(12) << a;

template <class T> void chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> void chmax(T& a, const T& b) { return b > a ? a = b, 1 : 0; }

template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T> using max_queue = priority_queue<T, vector<T>, less<T>>;

template <class T> using V = vector<T>;
using vi = V<int>;
using vd = V<ld>;
using vb = V<bool>;
using vpi = V<pi>;
using vvi = V<vi>;
using vvb = V<vb>;

const int mod = 1e9 + 7; // 998244353 1e9 + 7
const ll inf = (int)(1e18) + 7;
const int inf_s = 1e9 + 7;
const ld eps = 1e-9;

const int B = 32;
const int N = 1000 + 3;
const int logn = 20;
const int maxn = 2e5 + 7;
/////////////////////////solve/////////////////////////

pi e[maxn];

struct DSU {
    vi p, sz, len;
    DSU(int n) {
        p.resize(n), sz.resize(n, 1);
        len.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
    }
    pi get(int a) {
        if (a != p[a]) {
            pi res = get(p[a]);
            p[a] = res.first;
            len[a] ^= res.second;
        }
        return {p[a], len[a]};
    }
    bool unite(int aa, int bb) {
        auto [a, x] = get(aa);
        auto [b, y] = get(bb);
        if (a == b) return x == y;
        if (sz[a] > sz[b]) swap(a, b);
        sz[b] += sz[a];
        p[a] = b;
        len[a] = x ^ y ^ 1;
        return 0;
    }
};

int ans[maxn];

void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    for (int i = 0; i < m; ++i) {
        int v, u;
        cin >> v >> u;
        --v; --u;

        e[i] = {v, u};
    }

    ans[m] = 0;
    DSU dsu(n);
    for (int i = m - 1; i >= 0; --i) {
        auto [v, u] = e[i];
        ans[i] = ans[i + 1] | dsu.unite(v, u);
    }

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

        if (l != 0) {
            for (int qi = 0; qi < q; ++qi) {
                int l, r;
                cin >> l >> r;
                --l; --r;

                bool ok = 0;
                DSU dsu(n);
                for (int i = 0; i < l; ++i) {
                    auto [v, u] = e[i];
                    dbg(v, u);
                    if (dsu.unite(v, u)) ok = 1;
                }
                for (int i = r + 1; i < m; ++i) {
                    auto [v, u] = e[i];
                    dbg(v, u);
                    if (dsu.unite(v, u)) ok = 1;
                }

                cout << (ok ? "YES" : "NO") << "\n";
            }
            continue;
        }

        cout << (ans[r + 1] ? "YES" : "NO") << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef ONPC
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; ++i) {
#ifdef ONPC
        cerr << "===========" << i << "===========" << '\n';
#endif
        solve();
    }

#ifdef ONPC
    cerr << endl << "Time " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

Subtask #1
0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	2396 KB	Output is correct
2	Correct	2396 KB	Output is correct
3	Incorrect	2396 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	2396 KB	Output is correct
2	Correct	2396 KB	Output is correct
3	Incorrect	2396 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	57 ms	8012 KB	Output is correct
4	Correct	51 ms	10336 KB	Output is correct
5	Correct	54 ms	9812 KB	Output is correct
6	Correct	49 ms	8016 KB	Output is correct
7	Correct	52 ms	7884 KB	Output is correct
8	Correct	43 ms	7248 KB	Output is correct
9	Correct	45 ms	8272 KB	Output is correct
10	Correct	51 ms	10576 KB	Output is correct
11	Correct	46 ms	7948 KB	Output is correct
12	Correct	57 ms	9932 KB	Output is correct
13	Correct	46 ms	6228 KB	Output is correct
14	Correct	51 ms	6992 KB	Output is correct
15	Correct	49 ms	9040 KB	Output is correct
16	Correct	52 ms	10324 KB	Output is correct