oj.uz

Submission #689321

# Submission time Handle Problem Language Result Execution time Memory
689321 2023-01-28T07:11:02 Z zeroesandones Joker (BOI20_joker) C++17
25 / 100
 174 ms 13576 KB 
#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));
    }
};

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);

    vector<pi> query[201];
    FOR(i, 0, q) {
        ll l, r;
        cin >> l >> r;
        query[l].pb(r, i);
    }
    vector<bool> ans(q, false);

    FOR(i, 0, 201) {
        sort(all(query[i]), [&](pi x, pi y) {
                return x.fr > y.fr;
                });
    }

    FOR(T, 1, 201) {
        bool cyc = false;
        uf.init(n + 1);
        FOR(i, 1, min(T + 1, m + 1)) {
            if(uf.same(e[i].fr, e[i].sc)) {
                pi A = uf.find(e[i].fr);
                pi B = uf.find(e[i].sc);
                if(A.sc == B.sc) {
                    cyc = true;
                }
            } else {
                uf.unite(e[i].fr, e[i].sc);
            }
        }
        ll r = m;
        for(auto i : query[T]) {
            while(r > i.fr) {
                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[i.sc] = 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 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 0 ms 212 KB Output is correct
3 Correct 110 ms 10268 KB Output is correct
4 Correct 152 ms 13480 KB Output is correct
5 Correct 134 ms 12856 KB Output is correct
6 Correct 103 ms 10336 KB Output is correct
7 Correct 101 ms 10300 KB Output is correct
8 Correct 87 ms 9152 KB Output is correct
9 Correct 116 ms 10456 KB Output is correct
10 Correct 174 ms 13576 KB Output is correct
11 Correct 112 ms 10304 KB Output is correct
12 Correct 149 ms 12780 KB Output is correct
13 Correct 82 ms 8176 KB Output is correct
14 Correct 92 ms 9108 KB Output is correct
15 Correct 111 ms 11512 KB Output is correct
16 Correct 140 ms 13440 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -