답안 #765431

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765431	2023-06-24T13:04:56 Z	adrilen	Joker (BOI20_joker)	C++17	0 / 100	56 ms	9388 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;

constexpr int maxn = 2e5;

int siz[maxn] = { 0 }, par[maxn] = { 0 }, parity[maxn] = { 0 };
bool cycle[maxn] = { 0 };


int fnd(int p)
{
    if (p == par[p]) return p;
    return fnd(par[p]);
}

int fnd_parity(int p)
{
    if (p == par[p]) return 0;
    return fnd_parity(par[p]) ^ parity[p];
}

bool odd_cycle = false;

void uni(int a, int b)
{
    int aa = fnd(a), bb = fnd(b);

    if (aa == bb) {
        if (fnd_parity(a) == fnd_parity(b)) {
            // Odd cycle
            // cout << "\n";
            // cout << a << " " << b << " odd cycle\n";
            cycle[aa] = true;
            odd_cycle = true;
        } else {
            // Not odd cycle
        }
        return ;
    }

    if (siz[aa] > siz[bb]) {
        swap(a, b);
        swap(aa, bb);
    }
    
    // b > a
    parity[aa] = parity[a] ^ parity[b] ^ 1;
    par[aa] = bb;
    siz[bb] += siz[aa];

}

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

    for (int i = 0; i < n; i++) {
        siz[i] = 1;
        par[i] = i;
    }

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

        cin >> queries[i][0] >> queries[i][1];
        queries[i][0]--, queries[i][1]--;
        queries[i][2] = i;
    }
    

    vector <bool> output(q);
 
    reverse(edges.begin(), edges.end());
    // sort(queries.begin(), queries.end(), greater<arrr>());

    int breaking_point = n + 1;

    int a = 0;
    for (auto &i : edges)
    {
        // while (it != queries.end() && m - 1 - (*it)[1] == a)
        // {
        //     // cout << (*it)[2] << "\n";
        //     output[(*it)[2]] = odd_cycle;
        //     it++;
        // }


        
        uni(i[0], i[1]);

        if (odd_cycle) {breaking_point = a; break;}
        // cout << a << " " << (odd_cycle ? "YES" : "NO") << "\n";
        a++;
    }

    for (auto i : queries)
    {
        if (i[1] >= m - breaking_point - 1) cout << "NO";
        else cout <<"YES";
        cout << "\n";
    }

    // for (bool i : output) cout << (i ? "YES" : "NO") << "\n";



    // cout << par[0] << "\n";
    // for (int i = 0; i < n; i++) {
    //     cout << fnd_parity(i, parity[i]) << " ";
    // }
    // cout << "\n";
    // for (int i = 0; i < n; i++) {
    //     cout << par[i] << " ";
    // }
    // cout << "\n";
    
}

Subtask #1
0 / 6.0

#	결과	메모리	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Incorrect	212 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 8.0

#	결과	메모리	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Incorrect	212 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	55 ms	9388 KB	Output is correct
4	Correct	56 ms	8376 KB	Output is correct
5	Incorrect	56 ms	8140 KB	Output isn't correct
6	Halted	0 ms	0 KB	-