제출 #698960

#제출 시각아이디문제언어결과실행 시간메모리
698960safaricolaAlternating Heights (CCO22_day1problem1)C++17
11 / 25
230 ms13812 KiB
#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]; vector<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(rmv[a][it])continue; 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){ rmv[a[st]][a[st-1]]=1; }else{ rmv[a[st-1]][a[st]]=1; }/* 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]); rmv[a[i]][a[i-1]]=0; remov(); //cout<<"ans:"<<st<<' '<<i<<endl; mini[i]=st-1; }else{ adjl[a[i-1]].pb(a[i]); rmv[a[i-1]][a[i]]=0; 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"; } } /* 6 3 3 1 1 2 3 1 2 1 2 2 5 2 6 * 6 3 3 1 1 1 1 1 1 1 2 2 5 2 6 * 10 2 3 1 1 2 1 1 1 1 2 2 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...