oj.uz

Submission #445859

# Submission time Handle Problem Language Result Execution time Memory
445859 2021-07-19T23:44:35 Z Ozy Joker (BOI20_joker) C++17
0 / 100
 286 ms 23620 KB 
#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 3 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 3 ms 4940 KB Output is correct
3 Incorrect 3 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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