Submission #689313

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
689313	2023-01-28T06:41:29 Z	saayan007	Joker (BOI20_joker)	C++17	25 / 100	88 ms	17468 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Incorrect	3 ms	4948 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Incorrect	3 ms	4948 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	68 ms	11084 KB	Output is correct
4	Correct	77 ms	16972 KB	Output is correct
5	Correct	79 ms	17212 KB	Output is correct
6	Correct	82 ms	15032 KB	Output is correct
7	Correct	67 ms	15144 KB	Output is correct
8	Correct	64 ms	13628 KB	Output is correct
9	Correct	68 ms	14628 KB	Output is correct
10	Correct	73 ms	17100 KB	Output is correct
11	Correct	87 ms	15040 KB	Output is correct
12	Correct	74 ms	17076 KB	Output is correct
13	Correct	68 ms	13004 KB	Output is correct
14	Correct	67 ms	14124 KB	Output is correct
15	Correct	88 ms	16060 KB	Output is correct
16	Correct	76 ms	17468 KB	Output is correct