Submission #689317

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
689317	2023-01-28T06:56:19 Z	zeroesandones	Joker (BOI20_joker)	C++17	25 / 100	94 ms	11172 KB

Joker

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;

#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "

#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb emplace_back

struct UFDS {
    vi link, sz, len;
    int n;

    UFDS(int N) {
        init(N);
    }

    void init(int N) {
        n = N;
        link = vi(n);
        iota(all(link), 0);
        sz = vi(n, 1);
        len = vi(n, 0);
    }

    pi find(ll x) {
        if(link[x] == x)
            return {x, 0};
        pi val = find(link[x]);
        link[x] = val.fr;
        len[x] = (len[x] + val.sc) % 2;
        return {link[x], len[x]};
    }

    void unite(ll a, ll b) {
        pi A = find(a);
        pi B = find(b);
        if(A.fr == B.fr) return;
        if(sz[A.fr] < sz[B.fr]) swap(A, B);

        link[B.fr] = A.fr;
        len[B.fr] = (1 + A.sc + B.sc) % 2;
        sz[A.fr] += sz[B.fr];
    }

    bool same(ll a, ll b){
        return (find(a) == find(b));
    }
};

struct Q {
    int l, r, id;
};

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

    vector<pi> e(m + 1);
    FOR(i, 1, m + 1) {
        cin >> e[i].fr >> e[i].sc;
    }

    UFDS uf(n + 1);
    uf.init(n + 1);

    Q query[q];
    FOR(i, 0, q) {
        cin >> query[i].l >> query[i].r;
        query[i].id = i;
    }
    vector<bool> ans(q, false);

    sort(query, query + q, [&](Q x, Q y) {
        return x.r > y.r;
            });

    ll r = m;
    bool cyc = false;
    FOR(i, 0, q) {
        while(r > query[i].r) {
            if(uf.same(e[r].fr, e[r].sc)) {
                pi A = uf.find(e[r].fr);
                pi B = uf.find(e[r].sc);
                if(A.sc == B.sc) {
                    cyc = true;
                }
            } else {
                uf.unite(e[r].fr, e[r].sc);
            }
            --r;
        }
        ans[query[i].id] = cyc;
    }

    for(auto i : ans) {
        cout << (i ? "YES" : "NO") << nl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Incorrect	1 ms	212 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	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Incorrect	1 ms	212 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	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	77 ms	8688 KB	Output is correct
4	Correct	86 ms	11088 KB	Output is correct
5	Correct	87 ms	10696 KB	Output is correct
6	Correct	82 ms	8788 KB	Output is correct
7	Correct	82 ms	8780 KB	Output is correct
8	Correct	72 ms	7988 KB	Output is correct
9	Correct	84 ms	8916 KB	Output is correct
10	Correct	85 ms	11172 KB	Output is correct
11	Correct	94 ms	8792 KB	Output is correct
12	Correct	82 ms	10564 KB	Output is correct
13	Correct	80 ms	6904 KB	Output is correct
14	Correct	77 ms	7748 KB	Output is correct
15	Correct	85 ms	9648 KB	Output is correct
16	Correct	85 ms	11044 KB	Output is correct