oj.uz

Submission #129505

# Submission time Handle Problem Language Result Execution time Memory
129505 2019-07-12T11:13:17 Z davitmarg Friends (BOI17_friends) C++17
0 / 100
 1000 ms 5240 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
map<pair<int,int>,bool> edge;
int n,p,q,color[200005],lst[(1<<17)+5],c,mask[200005],dp[(1<<17)+5],pop[(1<<17)+5];
vector<int> g[200005];

void dfs(int v)
{
    color[v]=c;
    for(int i=0;i<g[v].size();i++)
	{
        int to=g[v][i];
        if(color[to])
            continue;
        dfs(to);
	}
}

void print(int msk)
{
	cout<<__builtin_popcount(msk)<<" ";
    for(int i=0;i<n;i++)
        if(((1<<i)&msk))
			cout<<i<<" ";
    cout<<endl;
}

int main()
{
    cin >> n >> p >> q;
    for(int i=0;i<n;i++)
	{
		int p;
		int m;
		scanf("%d",&m);
		while(m--)
		{
			scanf("%d",&p);
			g[i].PB(p);
			edge[MP(i,p)]=1;
            mask[i]|=(1<<p);
		}
	}
    for(int i=0;i<n;i++)
		for(int j=0;j<g[i].size();j++)
            if(edge[MP(i,g[j][j])]!=edge[MP(g[j][j],i)])
			{
				cout<<"detention"<<endl;
                return 0;
			}

    for(int i=0;i<n;i++)
        if(!color[i])
		{
            c++;
            dfs(i);
		}

    dp[0]=1;
    for(int i=1;i<(1<<n);i++)
		pop[i]=__builtin_popcount(i);
    for(int i=1;i<(1<<n);i++)
	{
        int cnt=0;
		dp[i]=1;
        if(pop[i]<p)
			continue;
		int col=-1;
        for(int j=0;j<n;j++)
        {
            if(((1<<j)&i)==0)
				continue;
            if(col==-1)
				col=color[j];
            if(color[j]!=col)
            {
            	dp[i]=0;
				break;
            }
            cnt+=pop[(((1<<j)|mask[j])^i)];
        }
		if(cnt>q)
            dp[i]=0;
	}
    for(int i=1;i<(1<<n);i++)
	{
        if(pop[i]<p)
			continue;
        vector<int> a;
        for(int j=0;j<n;j++)
            if(((1<<j)&i))
				a.PB(j);
        for(int j=0;j<(1<<a.size());j++)
		{
			int msk=0;
			if(pop[j]<p)
				continue;
            for(int k=0;k<a.size();k++)
                if(((1<<k)&j))
                    msk|=(1<<a[k]);
            if(dp[msk] && dp[i^msk])
			{
				dp[i]=1;
				lst[i]=msk;
				break;
			}
		}
	}
    if(!dp[(1<<n)-1])
		cout<<"detention"<<endl;
	else
	{
        int cnt=0;
		int msk=(1<<n)-1;
		while(msk)
		{
			cnt++;
			msk^=lst[msk];
		}
		cout<<"home\n"<<cnt<<endl;
		msk=(1<<n)-1;
		while(msk)
		{
			print(lst[msk]);
			msk^=lst[msk];
		}
	}

	return 0;
}


/*

5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13

*/

Compilation message

friends.cpp: In function 'void dfs(int)':
friends.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[i].size();j++)
               ~^~~~~~~~~~~~
friends.cpp:119:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0;k<a.size();k++)
                         ~^~~~~~~~~
friends.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&m);
   ~~~~~^~~~~~~~~
friends.cpp:59:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&p);
    ~~~~~^~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Execution timed out 1065 ms 4984 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Execution timed out 1049 ms 5216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Execution timed out 1049 ms 5216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Execution timed out 1065 ms 4984 KB Time limit exceeded
4 Halted 0 ms 0 KB -