Submission #1314703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314703		bearrbearr	Alternating Heights (CCO22_day1problem1)	C++20	17 / 25	1095 ms	4428 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define ii pair<int,int>
#define sec second
#define fir first

vector<int>adj[3002];
int deg[3002];
int n,k,qu;

bool topo(){
    queue<int>qu;
    for(int q=1;q<=k;q++){
        if(deg[q]==0)qu.push(q);
    }
    int hmm=0;

    while(!qu.empty()){
        int nd=qu.front(); qu.pop();
        hmm++;
        for(auto x : adj[nd]){
            deg[x]--;
            if(deg[x]==0)qu.push(x);
        }
    }

    return (hmm==k);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k>>qu;
    int a[n+1];
    for(int q=1;q<=n;q++){
        cin>>a[q];
    }

    int jauh[n+1];

    int pos=2;
    for(int q=1;q<=n;q++){
        int l=q,r=n;
        while(l<=r){
            int mid=(l+r)/2;
            for(int w=1;w<=k;w++){
                adj[w].clear(),deg[w]=0;
            }
            for(int w=q;w<mid;w++){
                if(w%2==0){
                    adj[a[w]].push_back(a[w+1]);
                    deg[a[w+1]]++;
                }
                else{
                    adj[a[w+1]].push_back(a[w]);
                    deg[a[w]]++;
                }
            }

            if(topo()){
                jauh[q]=mid;
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
    }

    while(qu--){
        int l,r;
        cin>>l>>r;
        if(jauh[l]>=r){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }

}

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 8