Submission #699106

#	Time	Username	Problem	Language	Result	Execution time	Memory
699106		safaricola	Alternating Heights (CCO22_day1problem1)	C++17	25 / 25	254 ms	15744 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 1; i <= n; i++) 
#define pb push_back
int n,a[3010],st=2,k,q,top[3010],cur,mini[3010],x,y;
bool rmv[3010][3010],vis[3010];
deque<int> adjl[3010];
bool ord(int a){
    if(vis[a] && top[a]==-1) return true;
    if(vis[a]) return false;
    vis[a] = true;
    for (int it: adjl[a]){
        if(ord(it)){
        return true;
        }
    }
    cur++;
    top[a]=cur;
    return false;
}
void remov(){
    bool flag=true;
    while(flag){
        flag=false;
        cur=0;
        memset(top, -1, sizeof(top));
        memset(vis, 0, sizeof(vis));
        for(int i=1; i<=n; i++)
            if(!vis[i]) 
                if(ord(i)){
                    flag=true;
                    i=n+1;
                    break;
                }
        if(flag){
            //cout<<st<<">\n";
            //remove edge;
            assert(st<=n+1);
            if(st%2==1){
                adjl[a[st]].pop_front();
            }else{
                adjl[a[st-1]].pop_front();
            }/*
            rep(i,n)
            for (int it: adjl[i]){
                if(rmv[i][it]) cout<<"rem "<<i<<' '<<it<<endl;
                else cout<<i<<' '<<it<<endl;
            }*/
            st++;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n>>k>>q;
    mini[1]=1;
    rep(i,n){
        cin>>a[i];
        if(i==1)continue;
        if(i%2==1){
            adjl[a[i]].pb(a[i-1]);
            remov();
            //cout<<"ans:"<<st<<' '<<i<<endl;
            mini[i]=st-1;
        }else{
            adjl[a[i-1]].pb(a[i]);
            remov();
            //cout<<"ans:"<<st<<' '<<i<<endl;
            mini[i]=st-1;
        }
    }
    while(q--){
        cin>>x>>y;
        if(x<mini[y])cout<<"NO\n";
        else cout<<"YES\n";
    }
}

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