Submission #1370626

#TimeUsernameProblemLanguageResultExecution timeMemory
1370626eradaxFriends (BOI17_friends)C++20
37 / 100
580 ms17276 KiB
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using bs=bitset<250>;
int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n,p,q;cin>>n>>p>>q;
    vector<vector<int>> mat(n,vector<int>(n));
    for(int i=0;i<n;i++){
        int m;cin>>m;
        int j;while(m--)cin>>j,mat[i][j]=1;
    }

    int f=1;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)f&=mat[i][j]==mat[j][i];
    if(!f){
        cout<<"detention\n";
        return 0;
    }

    vector<vector<pair<int,int>>> adj(n);
    vector<pair<int,int>> ed;
    int tim=0;
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(mat[i][j])
        adj[i].push_back({j,tim}),adj[j].push_back({i,tim++}),ed.push_back({i,j});

    for(int i=0;i<n;i++)if(ssize(adj[i])>=p+q){
        cout<<"detention\n";
        return 0;
    }

    int m=ssize(ed);

    int l1,l2;
    vector<int> g(n);
    vector<bs> groups;
    vector<int> vis(n);
    auto dfs=[&](auto&& self,int u) -> void {
        vis[u]=tim;
        groups.back().set(u);
        if(!groups[g[u]][u])g[u]=ssize(groups)-1;
        for(auto[v,e]:adj[u])if(e!=l1&&e!=l2&&vis[v]!=tim)self(self,v);
    };
    if(q==2){
        for(l1=-1;l1<m;l1++)for(l2=l1;l2<m;l2++){
            tim++;
            for(int i=0;i<n;i++)if(vis[i]!=tim){
                groups.push_back({});
                dfs(dfs,i);
                if(groups.back().count()>p)groups.pop_back();
            }
        }
    }
    if(q==1){
        for(l1=-1;l1<m;l1++){
            l2=l1;
            tim++;
            for(int i=0;i<n;i++)if(vis[i]!=tim){
                groups.push_back({});
                dfs(dfs,i);
                if(groups.back().count()>p)groups.pop_back();
            }
        }
    }
    if(q==0){
        l2=l1=-1;
        tim++;
        for(int i=0;i<n;i++)if(vis[i]!=tim){
            groups.push_back({});
            dfs(dfs,i);
            if(groups.back().count()>p)groups.pop_back();
        }
    }

    for(int i=0;i<n;i++)if(!groups[g[i]][i]){
        cout<<"detention\n";
        return 0;
    }

    sort(begin(g),end(g));g.erase(unique(begin(g),end(g)),end(g));
    for(int g1:g)for(int g2:g){
        if(g1<=g2)continue;
        bs a=groups[g1]&~groups[g2];
        bs b=groups[g2]&~groups[g1];

        int qp=0;
        for(int j=0;j<n;j++)if(a[j])for(auto[v,e]:adj[j])qp+=1-a[v];
        if(qp<=q)groups[g1]=a;
        else groups[g2]=b;
    }

    vector<bs> g2;
    for(int i:g)if(groups[i].count())g2.push_back(groups[i]);
    cout<<"home\n";
    cout<<ssize(g2)<<'\n';
    for(bs b:g2){
        cout<<b.count()<<' ';
        for(int i=0;i<n;i++)if(b[i])cout<<i<<' ';
        cout<<'\n';
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...