| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 310654 | 2020-10-07T14:37:56 Z | MrDomino | Political Development (BOI17_politicaldevelopment) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
const int N=50000+7;
int n;
int k;
int sol;
vector<int> g[N];
set<pair<int,int>> s;
void del(int x)
{
for (auto &i : g[x])
{
vector<int> gnew_i;
for (auto &y : g[i])
{
if (y!=x)
gnew_i.push_back(y);
}
s.erase({(int) g[i].size(),i});
s.insert({(int) g[i].size()-1,i});
g[i]=gnew_i;
}
g[x].clear();
}
bool on[N];
int sum[N];
int cur;
void bkt(int node)
{
cur++;
for (auto &it : g[node])
sum[it]++;
on[node]=1;
if (cur>sol)
sol=cur;
int possible=0;
for (auto &x : g[node])
{
if ((cur==1||node>x)on[x]==0&&sum[x]==cur)
{
possible++;
}
}
if (cur+possible<=sol)
{
on[node]=0;
cur--;
for (auto &it : g[node])
sum[it]--;
return;
}
for (auto &x : g[node])
{
if ((cur==1||node>x)on[x]==0&&sum[x]==cur)
{
bkt(x);
}
}
on[node]=0;
cur--;
for (auto &it : g[node])
sum[it]--;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for (int i=0;i<n;i++)
{
int l;
cin>>l;
for (int j=1;j<=l;j++)
{
int x;
cin>>x;
g[i].push_back(x);
}
sort(g[i].begin(),g[i].end());
s.insert({(int)g[i].size(),i});
}
while (!s.empty())
{
auto it=*s.begin();
s.erase(it);
int node=it.second;
bkt(node);
del(node);
}
cout<<sol<<"\n";
}