oj.uz

Submission #851642

# Submission time Handle Problem Language Result Execution time Memory
851642 2023-09-20T10:05:44 Z khanhphucscratch Alternating Heights (CCO22_day1problem1) C++14
0 / 25
 208 ms 38580 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int> ad[3001];
int k, c[3001], f[3001], a[3001], val[3001], pre[3001][3001], state[3001];
bool ok = 1;
void dfs(int u)
{
    state[u] = 1;
    for(int v : ad[u]) if(state[v] < 2){
        if(state[v] == 1){ok = 0; return;}
        else{
            dfs(v);
            if(ok == 0) return;
        }
    }
    state[u] = 2;
}
bool check(int l, int r)
{
    for(int i = 1; i <= k; i++){
        ad[i].clear();
        f[i] = 0; state[i] = 0; c[i] = 0;
    }
    for(int i = l; i <= r; i++){
        c[a[i]]++;
        if(i%2 == 1){
            if(i-1 >= l){
                ad[a[i]].push_back(a[i-1]);
                f[a[i-1]]++;
            }
            if(i+1 <= r){
                ad[a[i]].push_back(a[i+1]);
                f[a[i+1]]++;
            }
        }
    }
    ok = 0;
    int root = 1;
    for(int i = 1; i <= k; i++) if(f[i] == 0 && c[i] > 0){
        ok = 1;
        dfs(i);
        if(ok == 0) return 0;
    }
    return ok;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin>>n>>k>>q;
    map<pair<int, int>, int> f;
    for(int i = 1; i <= n; i++) cin>>a[i];
    int j = 1;
    for(int i = 1; i <= n; i++){
        while(j <= n && check(i, j) == 1) j++;
        val[i] = j;
    }
    for(int i = 1; i <= n; i++){
        pre[i][i] = val[i];
        for(int j = i+1; j <= n; j++) pre[i][j] = min(pre[i][j-1], val[j]);
    }
    cout<<val[1]<<endl;
    for(int i = 1; i <= q; i++){
        int l, r;
        cin>>l>>r;
        if(pre[l][r] <= r) cout<<"NO"<<'\n';
        else cout<<"YES"<<'\n';
    }
}

Compilation message

Main.cpp: In function 'bool check(int, int)':
Main.cpp:38:9: warning: unused variable 'root' [-Wunused-variable]
   38 |     int root = 1;
      |         ^~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 8.0

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