Submission #765451

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
765451	2023-06-24T13:37:46 Z	adrilen	Joker (BOI20_joker)	C++17	25 / 100	65 ms	6572 KB

Joker

#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_size; // >= 0 -> ind, < 0 -> siz
    vector <int> parity;

    bool has_odd_cycle;

    UnionFind(int n, int m)
    {
        par_size.assign(n, -1);
        parity.assign(n, 0);
        has_odd_cycle = false;
    }

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

        pii o = fnd(par_size[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)
        {
            if (a_parity == b_parity)
            {
                // Odd cycle
                return true;
            } else {
                return false;
            }
        }


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

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

        return false;
    }


} ;


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

    UnionFind Graph(n, m);

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

    reverse(edges.begin(), edges.end());

    int a = 0;
    for (auto &i : edges)
    {
        if (Graph.uni(i[0], i[1])) break;
        a++;
    }

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


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

Subtask #1
0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Incorrect	316 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Incorrect	316 KB	Output isn't correct
4	Halted	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	53 ms	5620 KB	Output is correct
4	Correct	55 ms	6284 KB	Output is correct
5	Correct	65 ms	6220 KB	Output is correct
6	Correct	60 ms	5520 KB	Output is correct
7	Correct	51 ms	5624 KB	Output is correct
8	Correct	49 ms	5472 KB	Output is correct
9	Correct	50 ms	5664 KB	Output is correct
10	Correct	58 ms	6572 KB	Output is correct
11	Correct	52 ms	5580 KB	Output is correct
12	Correct	54 ms	6164 KB	Output is correct
13	Correct	52 ms	4900 KB	Output is correct
14	Correct	51 ms	5216 KB	Output is correct
15	Correct	52 ms	5836 KB	Output is correct
16	Correct	54 ms	6312 KB	Output is correct