# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
924444 | Muhammad_Aneeq | Political Development (BOI17_politicaldevelopment) | C++17 | 3053 ms | 6228 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.
/*
بسم الله الرحمن الرحيم
Author:
(:Muhammad Aneeq:)
*/
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int const N=6e4+10;
vector<int>nei[N]={};
int res[N]={};
bool vis[N]={};
vector<int>f;
int n,k,ans=0;;
void dfs(int n)
{
if (f.size()==k)
return;
vis[n]=1;
f.push_back(n);
for (auto j:nei[n])
res[j]++;
for (auto i:f)
{
if (res[i]!=f.size()-1)
{
for (auto j:nei[n])
res[j]--;
f.pop_back();
vis[n]=0;
return;
}
}
for (auto j:nei[n])
{
if (!vis[j])
dfs(j);
}
ans=max(ans,int(f.size()));
for (auto j:nei[n])
res[j]--;
f.pop_back();
vis[n]=0;
}
inline void solve()
{
cin>>n>>k;
for (int i=0;i<n;i++)
{
int d;
cin>>d;
while (d--)
{
int x;
cin>>x;
if (i!=x)
nei[i].push_back(x);
}
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
vis[i]=0;
dfs(i);
}
cout<<min(ans,k)<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
solve();
}
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... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |