oj.uz

Submission #1054262

# Submission time Handle Problem Language Result Execution time Memory
1054262 2024-08-12T08:13:04 Z Mighilon Joker (BOI20_joker) C++17
25 / 100
 232 ms 23768 KB 
#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
// #define cin fin
// #define cout fout
// const string FILE_NAME = ""; ifstream fin(FILE_NAME + ".in"); ofstream fout(FILE_NAME + ".out");
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const int MOD = 1e9 + 7;

vector<vi> adj;
vi edges, good;
vi color;
bool cycle = false;

void dfs(int u, int p, int c){
    if(color[u] != -1 && color[u] != c){
        cycle = true;
        return;
    }
    if(color[u] != -1)
        return;
    color[u] = c;
    trav(id, adj[u]){
        if(!good[id]) continue;
        int v = edges[id] ^ u;
        if(v == p)
            continue;
        dfs(v, u, c ^ 1);
    }
}

void solve(){
    int n, m, q;
    cin >> n >> m >> q;
    adj.resize(n);
    edges.resize(m);
    F0R(i, m){
        int a, b;
        cin >> a >> b;
        --a, --b;
        edges[i] = a ^ b;
        adj[a].pb(i);
        adj[b].pb(i);
    }
    color.resize(n);
    good.resize(m);
    auto f = [&](int a, int b){
        color = vector<int>(n, -1);
        F0R(i, m){
            if(i >= a && i <= b)
                good[i] = false;
            else good[i] = true;
        }
        cycle = false;
        F0R(i, n){
            if(color[i] == -1)
                dfs(i, -1, 1);
        }
        return cycle;
    };
    vector<array<int, 3>> queries(q);
    F0R(i, q){
        cin >> queries[i][0] >> queries[i][1];
        queries[i][0]--, queries[i][1]--;
        queries[i][2] = i;
    }
    sort(all(queries), [&](array<int, 3>& a, array<int, 3>& b) {return a[1] < b[1];});
    int l = 0, r = q - 1, point = -1;
    while(l <= r){
        int m = (l + r) / 2;
        if(f(queries[m][0], queries[m][1])){
            point = m;
            l = m + 1;
        }
        else{
            r = m - 1;
        }
    }
    if(point == -1){
        F0R(i, q){
            cout << "NO\n";
        }
    }
    else{
        F0R(i, point + 1)
            queries[i][0] = 1;
        FOR(i, point + 1, q)
            queries[i][0] = 0;
        sort(all(queries), [&](array<int, 3>& a, array<int, 3>& b){return a[2] < b[2];});
        F0R(i, q){
            if(queries[i][0] == 1)
                cout << "YES\n";
            else cout << "NO\n";
        }
    }
}
 
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 122 ms 15420 KB Output is correct
4 Correct 137 ms 23088 KB Output is correct
5 Correct 142 ms 20684 KB Output is correct
6 Correct 152 ms 17984 KB Output is correct
7 Correct 160 ms 17976 KB Output is correct
8 Correct 195 ms 16676 KB Output is correct
9 Correct 211 ms 19520 KB Output is correct
10 Correct 232 ms 23768 KB Output is correct
11 Correct 164 ms 17220 KB Output is correct
12 Correct 179 ms 20108 KB Output is correct
13 Correct 128 ms 13404 KB Output is correct
14 Correct 197 ms 16248 KB Output is correct
15 Correct 217 ms 19428 KB Output is correct
16 Correct 217 ms 20988 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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