Submission #445860

#	Time	Username	Problem	Language	Result	Execution time	Memory
445860		Ozy	Joker (BOI20_joker)	C++17	25 / 100	568 ms	24136 KiB

Joker

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << ' ' << a << endl;
#define debugsl(a) cout << #a << ' ' << a << ", ";

#define MAX 200000
#define des first
#define t second
#define num first
#define id second

lli n,m,q,a,b,res,ini,fin,mitad;
vector<pair<lli,lli> > hijos[MAX+2];
lli prof[MAX+2];
bool existe;

bool DFS(lli pos, lli padre,lli p,lli val) {
    lli c;
    bool que = false;

    prof[pos] = p;
    for (auto h : hijos[pos]) {

        if (h.des == padre || h.t < val) continue;

        if (prof[h.des] != 0) {
            c = prof[h.des] + p + 1;
            if (c%2 == 1) return true;
        }
        else que =  que|DFS(h.des,pos,p+1,val);

    }

    return que;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> q;
    rep(i,1,m) {
        cin >> a >> b;
        hijos[a].push_back({b,i});
        hijos[b].push_back({a,i});
    }

    //resuelve
    res = 0;
    ini = 1;
    fin = m;
    while (ini <= fin) {

        mitad = (ini+fin)/2;
        rep(i,1,n) prof[i] = 0;

        existe = false;
        rep(i,1,n) if (prof[i] == 0) existe = existe|DFS(i,0,1,mitad);

        if (existe) {
            res = mitad;
            ini = mitad+1;
        }
        else fin = mitad-1;
    }


    rep(i,1,q) {
        cin >> a >> b;
        if (b < res) cout << "YES\n";
        else cout << "NO\n";
    }
}

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