Cod sursa(job #3166383)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 8 noiembrie 2023 17:51:47
Problema Trie Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.37 kb
#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;
}