제출 #851642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851642		khanhphucscratch	Alternating Heights (CCO22_day1problem1)	C++14	0 / 25	208 ms	38580 KiB

Main

#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';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8