Submission #931440

#	Time	Username	Problem	Language	Result	Execution time	Memory
931440		qwusha	Joker (BOI20_joker)	C++17	39 / 100	115 ms	12884 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<ll, ll>>> g;
vector<bool> ok;
vector<ll> col;

void dfs(ll v, ll 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<ll> par, dist, sz;
    void init(ll n) {
        par.resize(n);
        dist.resize(n);
        sz.resize(n);
        for (ll i = 0; i < n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }
    ll get_par(ll v) {
        if (v == par[v])
            return v;
        ll ans = get_par(par[v]);
        dist[v] = (dist[par[v]] + dist[v]) % 2;
        par[v] = ans;
        return ans;
    }
    ll get_dist(ll v) {
        if (v == par[v])
            return 0;
        return (dist[v] + get_dist(par[v])) % 2;
    }
    void union_(ll v, ll u) {
        ll nv = get_par(v);
        ll 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);
            swap(u, v);
        }
        ll uu = get_dist(u), vv = get_dist(v);
        dist[nu] = (get_dist(u) + get_dist(v) + 1) % 2;
        par[nu] = nv;
        sz[nv] += sz[nu];
    }
};


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll 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 (ll i = 0; i < m; i++) {
            ll v, u;
            cin >> v >> u;
            g[v - 1].push_back({u - 1, i});
            g[u - 1].push_back({v - 1, i});
        }
        for (ll qw = 0; qw < q; qw++) {
            ll l, r;
            cin >> l >> r;
            for (ll i = 0; i < m; i++) {
                if (l - 1 <= i && i < r)
                    ok[i] = 0;
                else
                    ok[i] = 1;
            }
            for (ll i = 0; i < n; i++) {
                col[i] = -1;
            }
            bool check = 0;
            for (ll 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<ll, ll>> vert(m);
        for (ll i = 0; i < m; i++) {
            ll v, u;
            cin >> v >> u;
            vert[i] = {v - 1, u - 1};
        }
        reverse(vert.begin(), vert.end());
        ll val = -1;
        dsu dsu;
        dsu.init(n);
        for (ll i = 0; i < m; i++) {
            auto [v, u] = vert[i];
            ch = 0;
            dsu.union_(v, u);
            if (ch) {
                val = (m - i);
                break;
            }
        }
        //cout << val << endl;
        for (ll qw = 0; qw < q; qw++) {
            ll l, r;
            cin >> l >> r;
            if (r < val)
                cout << "YES" << '\n';
            else
                cout << "NO" << '\n';
        }
    }
}

Compilation message (stderr)

Joker.cpp: In member function 'void dsu::union_(ll, ll)':
Joker.cpp:66:12: warning: unused variable 'uu' [-Wunused-variable]
   66 |         ll uu = get_dist(u), vv = get_dist(v);
      |            ^~
Joker.cpp:66:30: warning: unused variable 'vv' [-Wunused-variable]
   66 |         ll uu = get_dist(u), vv = get_dist(v);
      |                              ^~

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