# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
638572 | morasha3 | Alternating Heights (CCO22_day1problem1) | C++17 | 1093 ms | 4372 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 int ll;
typedef double ld;
const ll mod=1e9+7;
#define endl '\n'
ll n,k,q,arr[3007];
bool f=0;
void 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);
}
}
if(n>q.size())
f=1;
}
int32_t main()
{
//freopen("jumping.in","r",stdin);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k>>q;
for(int i=0; i<n; i++)
cin>>arr[i];
ll m[n];
for(int i=0; i<n; i++)
m[i]=i;
for(int h=0; h<2; h++)
{
for(int i=h; i<n; i+=2)
{
ll r=i+1,c=0;
while(r<n)
{
vector<vector<ll>>adj(k);
for(int j=i; j<r; j++)
{
if (j % 2 == i % 2)
adj[arr[j]-1].push_back(arr[j + 1]-1);
else
adj[arr[j + 1]-1].push_back(arr[j]-1);
}
f=0;
dfs(adj);
if(f)
break;
r++;
}
m[i]=r-1;
}
}
while(q--)
{
ll 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... |