Submission #992455

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
992455	2024-06-04T13:33:32 Z	Fatonim	Joker (BOI20_joker)	C++17	25 / 100	64 ms	14420 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;

        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	Execution time	Memory	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Incorrect	1 ms	2396 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.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	Incorrect	1 ms	2396 KB	Output isn't correct
4	Halted	0 ms	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	49 ms	9560 KB	Output is correct
4	Correct	49 ms	13908 KB	Output is correct
5	Correct	52 ms	14164 KB	Output is correct
6	Correct	47 ms	12084 KB	Output is correct
7	Correct	47 ms	12116 KB	Output is correct
8	Correct	44 ms	10580 KB	Output is correct
9	Correct	45 ms	11600 KB	Output is correct
10	Correct	51 ms	14164 KB	Output is correct
11	Correct	56 ms	11860 KB	Output is correct
12	Correct	64 ms	14012 KB	Output is correct
13	Correct	44 ms	10068 KB	Output is correct
14	Correct	45 ms	10960 KB	Output is correct
15	Correct	54 ms	13008 KB	Output is correct
16	Correct	50 ms	14420 KB	Output is correct