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;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
ll n,k,d[50000];
vector<ll>adj[50000];
vector<vector<bool>>dis(50000,vector<bool>(50000,0));
bool check(vector<ll>v){
for(ll i=0;i<v.size();i++){
for(ll j=i+1;j<v.size();j++){
if(dis[v[i]][v[j]]==false){
return false;
}
}
}
return true;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>k;
set<ll>adj[n];
set<pair<ll,ll>>ord;
for(ll i=0;i<n;i++){
cin>>d[i];
ord.insert({d[i],i});
for(ll j=0;j<d[i];j++){
ll u;
cin>>u;
adj[i].insert(u);
dis[i][u]=true;
}
}
ll ans=1;
while(!ord.empty()){
auto [s,i]=*ord.begin();
ord.erase(ord.begin());
ll sz=adj[i].size();
ll p=(1ll<<sz);
vector<ll>v;
for(ll j=0;j<p;j++){
ll r=0;
for(auto x:adj[i]){
if(j&(1ll<<r)){
v.pb(x);
}
}
if(check(v)){
ans=max(ans,(ll)v.size()+1);
}
v.clear();
}
for(auto x:adj[i]){
ll y=adj[x].size();
adj[x].erase(i);
ord.erase({y,x});
ord.insert({y-1,x});
}
}
cout<<ans;
}
Compilation message (stderr)
politicaldevelopment.cpp: In function 'bool check(std::vector<long long int>)':
politicaldevelopment.cpp:16:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(ll i=0;i<v.size();i++){
| ~^~~~~~~~~
politicaldevelopment.cpp:17:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(ll j=i+1;j<v.size();j++){
| ~^~~~~~~~~
# | 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... |