oj.uz

Submission #914283

# Submission time Handle Problem Language Result Execution time Memory
914283 2024-01-21T14:11:26 Z 3as8 Joker (BOI20_joker) C++14
0 / 100
 0 ms 344 KB 
#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
#define fastIO cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false);

#define mid ((l + r) / 2)
#define lChild ((index * 2) + 1)
#define rChild ((index * 2) + 2)

using namespace std;

struct node {
    ll u, i;
};

bool bi(vector<vector<node> >& graph, vector<ll>& color, ll startIndex, ll p, ll col, ll l, ll r) {

    color[startIndex] = col;

    ll ret = true;
    for(auto [el, i] : graph[startIndex]) {
        if(el == p || (l <= i && i <= r)) continue;
        if(color[el] == -1) ret &= bi(graph, color, el, startIndex, !col, l, r);


        if(color[el] != -1 && color[el] == col) return false;
        if(color[el] != col) continue;

    }

    return ret;
}

bool check(vector<vector<node> >& graph, ll i) {

    ll n = graph.size();

    vector<ll> col(n, -1);

    ll ans = true;
    for(int j = 0; j < n; j++) {
        if(col[j] != -1) continue;
        ans &= bi(graph, col, j, -1, 0, 0, i);
    }

    return !ans;
}


void solve(ll _) {

    ll n, m, q; cin>>n>>m>>q;

    vector<vector<node> > graph(n);
    for(int i = 0; i < m; i++) {
        ll x, y; cin>>x>>y;
        x--; y--;

        graph[x].push_back({y, i});
        graph[y].push_back({x, i});
    }

    ll l = -1, r = m;
    while(l < r) {

        bool ckB = check(graph, mid - 1), ck = check(graph, mid), ckA = check(graph, mid + 1);

        if(ckB != ckA) {
            l = r = mid;
            break;
        }

        if(ck) r = mid - 1;
        else l = mid + 1;
    }

    bool is = check(graph, l);
    ll x = l;
   // cout<<" => "<<l<<" "<<r<<endl;

    for(int i = 0; i < q; i++) {
        ll l, r; cin>>l>>r;
        l--; r--;

        if( x < r) cout<<"NO"<<endl;
        else if(r < x) cout<<"YES"<<endl;
        else {
            cout<<(is ? "YES" : "NO")<<endl;
        }

    }

}

int main() {
    //fastIO

    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);

    ll t = 0; solve(t);
}

Compilation message

Joker.cpp: In function 'bool bi(std::vector<std::vector<node> >&, std::vector<long long int>&, long long int, long long int, long long int, long long int, long long int)':
Joker.cpp:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for(auto [el, i] : graph[startIndex]) {
      |              ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -