제출 #689313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
689313		saayan007	Joker (BOI20_joker)	C++17	25 / 100	88 ms	17468 KiB

Joker

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

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

#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 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;
    }

    UFDS uf(n + 1);
    ll odd_if = 0;
    ruf(i, m, 1) {
        if(!uf.makeEne(edge[i].fr, edge[i].sc)) {
            odd_if = i;
            break;
        }
    }

    while(q--) {
        ll l, r;
        cin >> l >> r;
        
        cout << (r < odd_if ? "YES" : "NO") << nl;
    }
}

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