Submission #725745

#TimeUsernameProblemLanguageResultExecution timeMemory
725745josanneo22Alternating Heights (CCO22_day1problem1)C++17
11 / 25
1065 ms75024 KiB
#include<bits/stdc++.h> using namespace std; #define int long long inline int rd(){ int x=0,w=1; char ch=getchar(); for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1; for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*w; } const int maxn = 3e3 + 4; int n; vector<int> adj[maxn]; vector<char> color; vector<int> parent; int cycle_start, cycle_end; bool dfs(int v) { color[v] = 1; for (int u : adj[v]) { if (color[u] == 0) { parent[u] = v; if (dfs(u)) return true; } else if (color[u] == 1) { cycle_end = v; cycle_start = u; return true; } } color[v] = 2; return false; } vector<int> find_cycle() { color.assign(n, 0); parent.assign(n, -1); cycle_start = -1; for (int v = 0; v < n; v++) { if (color[v] == 0 && dfs(v)) break; } if (cycle_start == -1) { return { -1 }; } else { vector<int> cycle; cycle.push_back(cycle_start); for (int v = cycle_end; v != cycle_start; v = parent[v]) cycle.push_back(v); cycle.push_back(cycle_start); reverse(cycle.begin(), cycle.end()); return cycle; } } void solve(){ int k,q; cin>>n>>k>>q; vector<int> a(n); for(auto&x:a) cin>>x; if(k==2){ int ok[n+1][n+1]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ ok[i][j]=0; } } for(int i=0;i<n;i++){ ok[i][i]=1; for(int j=i+1;j<n;j++){ if(a[j]!=a[j-1]) ok[i][j]|=ok[i][j-1]; else{ ok[i][j]=0; break; } } } for(int queries=0;queries<q;queries++){ int l,r; cin>>l>>r; l--;r--; if(ok[l][r]) cout<<"YES\n"; else cout<<"NO\n"; } } else{ for(int queries=0;queries<q;queries++){ int l,r; cin>>l>>r; l--;r--; for(int i=0;i<n;i++) adj[i].clear(); int cnt=0; for(int i=l;i<=r;i++){ if(cnt%2==1){ if(i-1>=l)adj[a[i-1]].push_back(a[i]); if(i+1<=r) adj[a[i+1]].push_back(a[i]); } else{ if(i+1<=r) adj[a[i]].push_back(a[i+1]); if(i-1>=l) adj[a[i]].push_back(a[i-1]); } cnt++; } vector<int> ok=find_cycle(); int yeaaaa=(ok[0]==-1); if(yeaaaa) cout<<"YES\n"; else cout<<"NO\n"; } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int tt=1; //cin>>tt; while(tt--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...