Pagini recente » Cod sursa (job #146825) | Cod sursa (job #349723) | Cod sursa (job #2973050) | Cod sursa (job #3273154) | Cod sursa (job #3166383)
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int t;
int n;
vector < int > v[200005];
int nr;
int nrmut;
bool ok;
int grad[200005];
bool viz[200005];
int nrviz;
queue < int > q;
int dist[200005], k;
vector < int > sorttop;
int mx=-1;
void dfs(vector<int> &ed , vector<int> &pvis , vector<int> &vis , int i , int j)
{
if(pvis[i])
{
mx = max(mx , j - pvis[i]);
return;
}
if(!vis[i])
{
pvis[i] =j; j++; vis[i]=1;
if(ed[i]!=-1) dfs(ed , pvis , vis , ed[i],j);
}
pvis[i] = 0;
return;
}
int longestCycle(vector<int>& ed)
{
vector<int> vis(ed.size(),0) , pvis(ed.size(),0);
mx = -1;
for(int i=0;i<ed.size();i++)
{
if(!vis[i]) dfs(ed,pvis,vis,i,1);
}
return mx;
}
void dfs(int nod) {
viz[nod] = 1;
for (auto k:v[nod]) {
if (viz[k]==0) {
dfs(k);
}
else if (k==0) ok = 1;
}
}
void solve() {
ok = 0;
nrviz = 0;
sorttop.clear();
cin >> n >> k;
for (int i=0;i<=n;i++) {
v[i].clear();
grad[i] = 0;
viz[i] = 0;
dist[i] = 0;
}
for (int i=1;i<=n;i++) {
cin >> nr;
if (nr<=n) {
if (nr<=i) nrmut = i-nr;
else nrmut = i+n-nr;
v[nrmut].push_back((nrmut+nr)%n);
grad[(nrmut+nr)%n]++;
}
}
for (int i=0;i<n;i++) {
if (grad[i]==0) {
q.push(i);
}
}
if (grad[0]==0) ok = 0;
else {
while (q.empty()==0 && !ok) {
int nod = q.front();
q.pop();
sorttop.push_back(nod);
nrviz++;
viz[nod] = 1;
for (auto p:v[nod]) {
grad[p]--;
if (grad[p]==0) q.push(p);
}
}
while (q.empty()==0) q.pop();
dfs(0);
for (int i=0;i<sorttop.size();i++) {
for (auto p:v[sorttop[i]]) {
dist[p] = max(dist[p], dist[sorttop[i]]+1);
if (dist[p]>=k && p==0) ok = 1;
}
}
}
if (ok==1) cout << "Yes\n";
else cout << "No\n";
}
int main()
{
cin >> t;
for (int w = 1; w <= t; w++) {
solve();
}
return 0;
}