oj.uz

Submission #759312

# Submission time Handle Problem Language Result Execution time Memory
759312 2023-06-16T05:56:34 Z boyliguanhan Joker (BOI20_joker) C++17
0 / 100
 125 ms 15964 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define N 200100
vector<int> adj[N];
int color[N], ans[N], a[N], b[N], n, m, q, sz[200];
pair<int, int> arr[200][N];
int dfs(int x, int col) {
    if(color[x]) {
        if(col==color[x]) return 0;
        else return 1;
    }
    color[x] = col;
    for(auto i: adj[x]) 
        if(dfs(i, 3-col))
            return 1;
    return 0;
}
bool check(int l, int r) {
    memset(color, 0, sizeof color);
    for(int i = 1; i <= n; i++)
        adj[i].clear();
    for(int i = 0; i < l; i++)
        adj[a[i]].push_back(b[i]), adj[b[i]].push_back(a[i]);
    for(int i = r+1; i < m; i++)
        adj[a[i]].push_back(b[i]), adj[b[i]].push_back(a[i]);
    for(int i = 0; i < n; i++)
        if(!color[i])
            if(dfs(i, 1))
                return 1;
    return 0;
}
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    for(int i = 0; i < m; i++)
        cin >> a[i] >> b[i];
    for(int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        arr[l-1][sz[l-1]].first = r-1;
        arr[l-1][sz[l-1]++].second = i;
    }
    for(int i = 0; i < m; i++) {
        sort(arr[i], arr[i] + sz[i]);
        int l = 0, r = sz[i]-1;
        while(l<r) {
            int mid = l+r>>1;
            if(check(i, arr[i][mid].first)) {
                l = mid+1;
            } else {
                r = mid;
            }
        }
        for(int j = 0; j < l; j++)
            ans[arr[i][j].second] = 1;
        for(int j = l; j < sz[i]; ++j)
            ans[arr[i][j].second] = 0;
    }
    for(int i = 0; i < q; i++)
        cout << (ans[i]?"YES\n":"NO\n");
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:49:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |             int mid = l+r>>1;
      |                       ~^~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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