oj.uz

답안 #689350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
689350 2023-01-28T09:34:35 Z zeroesandones Joker (BOI20_joker) C++17
0 / 100
 100 ms 10372 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 100 ms 10372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 -