Submission #445860

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
445860	2021-07-19T23:47:41 Z	Ozy	Joker (BOI20_joker)	C++17	25 / 100	568 ms	24136 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Incorrect	3 ms	4940 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	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Incorrect	3 ms	4940 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	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	276 ms	19680 KB	Output is correct
4	Correct	432 ms	23484 KB	Output is correct
5	Correct	362 ms	22852 KB	Output is correct
6	Correct	331 ms	22188 KB	Output is correct
7	Correct	334 ms	20988 KB	Output is correct
8	Correct	323 ms	22516 KB	Output is correct
9	Correct	409 ms	22548 KB	Output is correct
10	Correct	559 ms	23064 KB	Output is correct
11	Correct	343 ms	22720 KB	Output is correct
12	Correct	468 ms	22444 KB	Output is correct
13	Correct	193 ms	21264 KB	Output is correct
14	Correct	322 ms	22928 KB	Output is correct
15	Correct	505 ms	24136 KB	Output is correct
16	Correct	568 ms	23456 KB	Output is correct