Submission #689324

#	Time	Username	Problem	Language	Result	Execution time	Memory
689324		saayan007	Joker (BOI20_joker)	C++17	39 / 100	2070 ms	11844 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

using ll = int;
using pi = pair<int, int>;
using pl = pair<int, int>;
using vi = vector<int>;
using vl = vector<int>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<int, int>>;

#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first 
#define sc second
#define mp make_pair
#define pb emplace_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const ll mxn = 2e5L + 1;
ll n, m, Q;
vpl adj[mxn];
bool vis[mxn] = {};
ll dep[mxn] = {};

struct Query {
    ll l, r, idx;
};

inline bool operator<(Query &lt, Query &rt) {
    if(lt.l != rt.l)
        return lt.l < rt.l;
    return lt.r > rt.r;
}

struct UFDS {
    vl sz;
    vl lnk;
    vl ene;

    UFDS(ll N) {
        sz = vl(N, 1);
        lnk = vl(N);
        iota(all(lnk), 0);
        ene = vl(N, -1);
    }

    ll find(ll a) {
        if(a == lnk[a]) {
            return a;
        }

        return lnk[a] = find(lnk[a]);
    }

    bool same(ll a, ll b) {
        return find(a) == find(b);
    }

    ll unite(ll a, ll b) {
        a = find(a);
        b = find(b);

        if(a == b)
            return a;

        if(sz[a] < sz[b])
            swap(a, b);

        lnk[b] = a;
        sz[a] += sz[b];

        return a;
    }

    bool makeEne(ll a, ll b) {
        a = find(a);
        b = find(b);

        if(a == b) {
            return 0;
        }
        if(ene[a] == b) {
            return 1;
        }

        ll c = ene[a];
        ll d = ene[b];

        if(d != -1)
            a = unite(a, d);
        if(c != -1)
            b = unite(b, c);

        ene[a] = b;
        ene[b] = a;

        return 1;
    }
};

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> Q;
    pl edge[m + 1];
    fur(i, 1, m) {
        cin >> edge[i].fr >> edge[i].sc;
    }

    Query q[Q];
    fur(rep, 0, Q - 1) {
        cin >> q[rep].l >> q[rep].r;
        q[rep].idx = rep;
    }

    bool ans[Q] = {};
    sort(q, q + Q);
    fur(i, 0, Q - 1) {
        ll j = i;
        while(j + 1 < Q && q[j + 1].l == q[i].l) {
            ++j;
        }

        bool yes = 0;
        UFDS uf(n + 1);
        fur(x, 1, q[i].l - 1) {
            yes |= !uf.makeEne(edge[x].fr, edge[x].sc);
        }

        ll cur_r = m;
        fur(x, i, j) {
            while(cur_r > q[x].r) {
                yes |= !uf.makeEne(edge[cur_r].fr, edge[cur_r].sc);
                --cur_r;
            } 
            ans[q[x].idx] = yes;
        }
        i = j;
    }

    for(auto u : ans) {
        cout << (u ? "YES" : "NO") << nl;
    }
}

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