oj.uz

답안 #765480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
765480 2023-06-24T14:34:46 Z adrilen Joker (BOI20_joker) C++17
25 / 100
 66 ms 9612 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 2> arr;
typedef array<int, 3> arrr;

struct UnionFind {
    vector <int> par; // >= 0 -> ind, < 0 -> siz
    vector <int> parity;
    vector <int> siz;

    vector <arr> history;

    UnionFind(int n, int m)
    {
        par.assign(n, -1);
        parity.assign(n, 0);
        siz.assign(n, 1);
    }

    pii fnd(int p)
    {
        if (par[p] < 0) return {p, 0};

        pii o = fnd(par[p]);
        o.second ^= parity[p];
        return o;
    }

    bool uni(int a, int b) // Return whether this will be an odd cycle
    {
        int a_parity, b_parity;
        tie(a, a_parity) = fnd(a);
        tie(b, b_parity) = fnd(b);

        if (a == b)
        {
            history.emplace_back(arr{-1, -1});
            if (a_parity == b_parity)
            {
                // Odd cycle
                return true;
            } else {
                return false;
            }
        }


        if (siz[a] < siz[b]) swap(a, b);
        // a > b
        // b will be merged into b

        siz[a] += siz[b];
        parity[b] = a_parity ^ b_parity ^ 1;
        par[b] = a;

        history.emplace_back(arr{a, b});
        return false;
    }

    void undo()
    {
        arr p = history.back();
        history.pop_back();
        if (p[0] == -1) return ;

        siz[p[0]] -= siz[p[1]];
        parity[p[1]] = 0;
        par[p[1]] = -1;
    }
} ;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m, q;
    cin >> n >> m >> q;

    vector<arr> edges(m);
    for (auto &i : edges) {
        cin >> i[0] >> i[1];
        i[0]--, i[1]--;
    }

    int b = 0;
    vector <arrr> queries(q);
    for (auto &i : queries)
    {
        cin >> i[0] >> i[1];
        i[0]--, i[1]--;
        i[2] = b++;
    }

    // Starting with the queries the furthest to the right
    sort(queries.begin(), queries.end(), [] (const auto &lhs, const auto &rhs)
    {
        return lhs[1] > rhs[1];
    });

    vector <int> output(q);

    UnionFind Graph(n, m);

    // const int max_range = 200;
    
    bool have_found_cycle = false, this_cycle;

    auto right_edge = edges.end() - 1;
    auto left_edge = edges.begin();
    for (auto &i : queries)
    {
        if (have_found_cycle) {
            output[i[2]] = true;
            continue;
        }

        // The right side

        // Check if the right amount
        while (right_edge - edges.begin() > i[1]) {
            if (Graph.uni((*right_edge)[0], (*right_edge)[1])) {
                // All queries after this will be true
                have_found_cycle = true;
            }
            right_edge--;
        }

        // The left side

        // left_edge = edges.begin();
        
        this_cycle = false;
        while (left_edge - edges.begin() < i[0])
        {
            if (Graph.uni((*left_edge)[0], (*left_edge)[1])) {
                this_cycle = true;
                break;
            }
            left_edge++;
        }
        
        output[i[2]] = (this_cycle || have_found_cycle);

        // Remove last edges
        while (left_edge != edges.begin())
        {
            Graph.undo();
            left_edge--;
        }

    }

    for (auto &i : output) cout << (i ? "YES" : "NO") << "\n";

    // for (auto &i : queries)
    // {
    //     cout << (i[1] < a ? "YES" : "NO") << "\n";
    // }
}

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 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 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 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 62 ms 7652 KB Output is correct
4 Correct 65 ms 9612 KB Output is correct
5 Correct 63 ms 8056 KB Output is correct
6 Correct 62 ms 7644 KB Output is correct
7 Correct 62 ms 7676 KB Output is correct
8 Correct 62 ms 7324 KB Output is correct
9 Correct 61 ms 7808 KB Output is correct
10 Correct 63 ms 8960 KB Output is correct
11 Correct 62 ms 7624 KB Output is correct
12 Correct 63 ms 8572 KB Output is correct
13 Correct 62 ms 6748 KB Output is correct
14 Correct 62 ms 7224 KB Output is correct
15 Correct 64 ms 8152 KB Output is correct
16 Correct 66 ms 8844 KB Output is correct

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 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 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 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 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 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -