# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
638582 | morasha3 | Alternating Heights (CCO22_day1problem1) | C++17 | 1090 ms | 4276 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef double ld;
#define endl '\n'
bool dfs(vector<vector<int>>& v)
{
int n = v.size();
vector<int> deg(n);
for (int a = 0; a < n; a++)
for (int b : v[a])
deg[b]++;
vector<int> q;
q.reserve(n);
for (int i = 0; i < n; i++)
if (deg[i] == 0)
q.push_back(i);
for (int rep = 0; rep < q.size(); rep++)
{
int c = q[rep];
for (auto nxt : v[c])
{
deg[nxt]--;
if (deg[nxt] == 0)
q.push_back(nxt);
}
}
return n>q.size();
}
int32_t main()
{
//freopen("jumping.in","r",stdin);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k,q;
cin>>n>>k>>q;
int arr[n];
for(int i=0; i<n; i++)
{cin>>arr[i]; arr[i]--;}
int m[n];
for(int h:{0,1})
{
for(int i=h; i<n; i+=2)
{
int r=i+1,c=0;
while(r<n)
{
vector<vector<int>>adj(k);
for(int j=i; j<r; j++)
{
if (j % 2 == i % 2)
adj[arr[j]].push_back(arr[j + 1]);
else
adj[arr[j + 1]].push_back(arr[j]);
}
if(dfs(adj))
break;
r++;
}
m[i]=r-1;
}
}
while(q--)
{
int a,b;
cin>>a>>b;
a--,b--;
if(m[a]>=b)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |