Submission #931419

#	Time	Username	Problem	Language	Result	Execution time	Memory
931419		qwusha	Joker (BOI20_joker)	C++17	14 / 100	115 ms	5120 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;
    }
}


struct dsu {
    vector<int> par, dist, sz;
    void init(int n) {
        par.resize(n);
        dist.assign(n, 0);
        sz.assign(n, 1);
        for (int i = 0; i < n; i++) {
            par[i] = i;
        }
    }
    int get_par(int v) {
        if (v == par[v])
            return v;
        int ans = get_par(par[v]);
        dist[v] = (dist[v] + dist[par[v]]) % 2;
        par[v] = ans;
        return ans;
    }
    int get_dist(int v) {
        if (v == par[v])
            return 0;
        return (dist[v] + get_dist(par[v])) % 2;
    }
    void union_(int v, int u) {
        int nv = get_par(v);
        int nu = get_par(u);
        if (nv == nu) {
            if (get_dist(v) == get_dist(u))
                ch = 1;
            return;
        }
        if (sz[nu] > sz[nv])
            swap(nv, nu);
        par[nu] = nv;
        dist[nu] = 1;
    }
};


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, q;
    cin >> n >> m >> q;
    if (n <= 2000 && m <= 2000 && q <= 2000) {
        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';
            }
        }
    } else {
        vector<pair<int, int>> vert(m);
        for (int i = 0; i < m; i++) {
            int v, u;
            cin >> v >> u;
            vert[i] = {v - 1, u - 1};
        }
        reverse(vert.begin(), vert.end());
        int val = -1;
        dsu dsu;
        dsu.init(n);
        for (int i = 0; i < m; i++) {
            auto [v, u] = vert[i];
            ch = 0;
            dsu.union_(v, u);
            if (ch) {
                val = (m - i);
                break;
            }
        }
        for (int qw = 0; qw < q; qw++) {
            int l, r;
            cin >> l >> r;
            if (r < val)
                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