oj.uz

Submission #129616

# Submission time Handle Problem Language Result Execution time Memory
129616 2019-07-12T19:29:29 Z davitmarg Friends (BOI17_friends) C++17
20 / 100
 65 ms 10488 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,lst[(1<<17)+5],mask[200005],dp[(1<<17)+5],can[(1<<17)+5],pop[(1<<17)+5];
vector<int> g[200005];

void print(int msk)
{
	cout<<pop[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;
			}

    dp[0]=1;
    for(int i=1;i<(1<<n);i++)
		pop[i]=__builtin_popcount(i);
    for(int i=1;i<(1<<n);i++)
	{
        if(pop[i]>p)
			continue;
        int cnt=0;
		can[i]=1;
        for(int j=0;j<n;j++)
        {
            if(((1<<j)&i)==0)
				continue;
            cnt+=pop[i^(mask[j]|i)];
        }
		if(cnt>q)
            can[i]=0;
        dp[i]=can[i];
	}
    for(int i=1;i<(1<<n);i++)
	{
		int msk=i;
		while(msk>0)
		{
            if(can[msk] && dp[i^msk])
			{
				dp[i]=1;
				lst[i]=msk;
				break;
			}
			msk=(msk-1)&i;
		}
	}
    if(!dp[(1<<n)-1])
	{
		cout<<"detention"<<endl;
		return 0;
	}
	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 'int main()':
friends.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g[i].size();j++)
               ~^~~~~~~~~~~~
friends.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&m);
   ~~~~~^~~~~~~~~
friends.cpp:47:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&p);
    ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 16 ms 5496 KB Output is correct
5 Correct 49 ms 5880 KB Output is correct
6 Correct 65 ms 5752 KB Output is correct
7 Correct 65 ms 5752 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Runtime error 14 ms 10488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Runtime error 14 ms 10488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 16 ms 5496 KB Output is correct
5 Correct 49 ms 5880 KB Output is correct
6 Correct 65 ms 5752 KB Output is correct
7 Correct 65 ms 5752 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Runtime error 14 ms 10488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -