Submission #931405

#	Time	Username	Problem	Language	Result	Execution time	Memory
931405		qwusha	Joker (BOI20_joker)	C++17	14 / 100	2093 ms	16032 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef long double ld;
const ll inf = 1e9;
const ld eps = 1e-8;
const ll logs = 32;
#include <cmath>
bool ch = 0;
vector<vector<pair<int, int>>> g;
vector<bool> ok;
vector<int> col;

void dfs(int v, int c = 0) {
    col[v] = c;
    for (auto [u, ind] : g[v]) {
        if (!ok[ind]) {
            continue;
        }
        if (col[u] == -1)
            dfs(u, 1 - c);
        else if (col[u] == col[v])
            ch = 1;
    }
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, q;
    cin >> n >> m >> q;
    g.resize(n);
    ok.resize(m, 1);
    col.resize(n);
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        g[v - 1].push_back({u - 1, i});
        g[u - 1].push_back({v - 1, i});
    }
    for (int qw = 0; qw < q; qw++) {
        int l, r;
        cin >> l >> r;
        for (int i = 0; i < m; i++) {
            if (l - 1 <= i && i < r)
                ok[i] = 0;
            else
                ok[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            col[i] = -1;
        }
        bool check = 0;
        for (int i = 0; i < n; i++) {
            if (col[i] == -1) {
                ch = 0;
                dfs(i);
                if (ch)
                    check = 1;
            }
        }
        if (check) {
            cout << "YES" << '\n';
        } else {
            cout << "NO" << '\n';
        }
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29