답안 #162432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
162432	2019-11-08T08:48:55 Z	MvC	Political Development (BOI17_politicaldevelopment)	C++11	16 / 100	3000 ms	308104 KB

politicaldevelopment

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=5e4+5;
const int mod=1e9+7;
using namespace std;
int n,k,x,i,j,d[nmax],nr,rs,ts;
bitset<nmax>b[nmax],viz;
vector<int>g[nmax],vc,rnd;
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	srand(time(0));
	cin>>n>>k;
	for(i=1;i<=n;i++)
	{
		cin>>d[i];
		for(j=1;j<=d[i];j++)
		{
			cin>>x;
			x++;
			b[i][x]=1;
			//g[i].pb(x);
		}
	}
	for(i=1;i<=n;i++)rnd.pb(i);
	ts=200000000/(n+n*k);
	while(ts--)
	{
		random_shuffle(rnd.begin(),rnd.end());
		vc.clear();
		for(i=0;i<n;i++)
		{
			x=rnd[i];
			nr=0;
			for(j=0;j<(int)vc.size();j++)nr+=b[x][vc[j]];
			if(nr==(int)vc.size())vc.pb(x);
		}
		rs=max(rs,(int)vc.size());
		if(rs==k)break;
	}
	cout<<rs<<endl;
	return 0;
}

Compilation message

politicaldevelopment.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
politicaldevelopment.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1528 KB	Output is correct
2	Correct	3 ms	1528 KB	Output is correct
3	Correct	21 ms	22392 KB	Output is correct
4	Correct	24 ms	21596 KB	Output is correct
5	Correct	21 ms	21624 KB	Output is correct
6	Correct	50 ms	21724 KB	Output is correct
7	Correct	21 ms	21664 KB	Output is correct
8	Correct	2641 ms	1700 KB	Output is correct
9	Correct	3 ms	1528 KB	Output is correct
10	Correct	403 ms	1716 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1528 KB	Output is correct
2	Correct	3 ms	1528 KB	Output is correct
3	Correct	21 ms	22392 KB	Output is correct
4	Correct	24 ms	21596 KB	Output is correct
5	Correct	21 ms	21624 KB	Output is correct
6	Correct	50 ms	21724 KB	Output is correct
7	Correct	21 ms	21664 KB	Output is correct
8	Correct	2641 ms	1700 KB	Output is correct
9	Correct	3 ms	1528 KB	Output is correct
10	Correct	403 ms	1716 KB	Output is correct
11	Correct	20 ms	21692 KB	Output is correct
12	Correct	2494 ms	21708 KB	Output is correct
13	Correct	1874 ms	1580 KB	Output is correct
14	Correct	2416 ms	21700 KB	Output is correct
15	Correct	3 ms	1528 KB	Output is correct
16	Correct	2419 ms	21756 KB	Output is correct
17	Correct	3 ms	1528 KB	Output is correct
18	Correct	2434 ms	21880 KB	Output is correct
19	Correct	1973 ms	1708 KB	Output is correct
20	Correct	120 ms	21624 KB	Output is correct
21	Correct	854 ms	21768 KB	Output is correct
22	Correct	1977 ms	1716 KB	Output is correct
23	Correct	200 ms	22904 KB	Output is correct
24	Correct	2041 ms	1728 KB	Output is correct
25	Correct	70 ms	22776 KB	Output is correct
26	Correct	2446 ms	22264 KB	Output is correct
27	Correct	2491 ms	22832 KB	Output is correct
28	Correct	2439 ms	21980 KB	Output is correct
29	Correct	2861 ms	22764 KB	Output is correct
30	Correct	2463 ms	22776 KB	Output is correct
31	Correct	2507 ms	23160 KB	Output is correct
32	Correct	2566 ms	22720 KB	Output is correct
33	Correct	2604 ms	23092 KB	Output is correct
34	Correct	2583 ms	23016 KB	Output is correct
35	Correct	2268 ms	12016 KB	Output is correct
36	Correct	2289 ms	12024 KB	Output is correct
37	Correct	2431 ms	12024 KB	Output is correct
38	Correct	2009 ms	6680 KB	Output is correct
39	Correct	2041 ms	6668 KB	Output is correct
40	Correct	60 ms	23288 KB	Output is correct
41	Correct	2083 ms	6648 KB	Output is correct
42	Correct	65 ms	23428 KB	Output is correct
43	Correct	65 ms	23344 KB	Output is correct

Subtask #3

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1574 ms	1704 KB	Output is correct
2	Correct	1142 ms	1656 KB	Output is correct
3	Correct	1133 ms	1644 KB	Output is correct
4	Correct	1338 ms	1612 KB	Output is correct
5	Correct	1157 ms	1640 KB	Output is correct
6	Correct	1167 ms	1640 KB	Output is correct
7	Correct	1164 ms	1656 KB	Output is correct
8	Correct	1151 ms	1644 KB	Output is correct
9	Correct	1162 ms	1656 KB	Output is correct
10	Correct	1151 ms	1644 KB	Output is correct
11	Incorrect	1999 ms	308104 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1528 KB	Output is correct
2	Correct	3 ms	1528 KB	Output is correct
3	Correct	21 ms	22392 KB	Output is correct
4	Correct	24 ms	21596 KB	Output is correct
5	Correct	21 ms	21624 KB	Output is correct
6	Correct	50 ms	21724 KB	Output is correct
7	Correct	21 ms	21664 KB	Output is correct
8	Correct	2641 ms	1700 KB	Output is correct
9	Correct	3 ms	1528 KB	Output is correct
10	Correct	403 ms	1716 KB	Output is correct
11	Correct	20 ms	21692 KB	Output is correct
12	Correct	2494 ms	21708 KB	Output is correct
13	Correct	1874 ms	1580 KB	Output is correct
14	Correct	2416 ms	21700 KB	Output is correct
15	Correct	3 ms	1528 KB	Output is correct
16	Correct	2419 ms	21756 KB	Output is correct
17	Correct	3 ms	1528 KB	Output is correct
18	Correct	2434 ms	21880 KB	Output is correct
19	Correct	1973 ms	1708 KB	Output is correct
20	Correct	120 ms	21624 KB	Output is correct
21	Correct	854 ms	21768 KB	Output is correct
22	Correct	1977 ms	1716 KB	Output is correct
23	Correct	200 ms	22904 KB	Output is correct
24	Correct	2041 ms	1728 KB	Output is correct
25	Correct	70 ms	22776 KB	Output is correct
26	Correct	2446 ms	22264 KB	Output is correct
27	Correct	2491 ms	22832 KB	Output is correct
28	Correct	2439 ms	21980 KB	Output is correct
29	Correct	2861 ms	22764 KB	Output is correct
30	Correct	2463 ms	22776 KB	Output is correct
31	Correct	2507 ms	23160 KB	Output is correct
32	Correct	2566 ms	22720 KB	Output is correct
33	Correct	2604 ms	23092 KB	Output is correct
34	Correct	2583 ms	23016 KB	Output is correct
35	Correct	2268 ms	12016 KB	Output is correct
36	Correct	2289 ms	12024 KB	Output is correct
37	Correct	2431 ms	12024 KB	Output is correct
38	Correct	2009 ms	6680 KB	Output is correct
39	Correct	2041 ms	6668 KB	Output is correct
40	Correct	60 ms	23288 KB	Output is correct
41	Correct	2083 ms	6648 KB	Output is correct
42	Correct	65 ms	23428 KB	Output is correct
43	Correct	65 ms	23344 KB	Output is correct
44	Correct	174 ms	24156 KB	Output is correct
45	Correct	1328 ms	1656 KB	Output is correct
46	Correct	1335 ms	23260 KB	Output is correct
47	Correct	1475 ms	24120 KB	Output is correct
48	Correct	2160 ms	23352 KB	Output is correct
49	Correct	1479 ms	24056 KB	Output is correct
50	Correct	1255 ms	23988 KB	Output is correct
51	Incorrect	1058 ms	24708 KB	Output isn't correct
52	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1528 KB	Output is correct
2	Correct	3 ms	1528 KB	Output is correct
3	Correct	21 ms	22392 KB	Output is correct
4	Correct	24 ms	21596 KB	Output is correct
5	Correct	21 ms	21624 KB	Output is correct
6	Correct	50 ms	21724 KB	Output is correct
7	Correct	21 ms	21664 KB	Output is correct
8	Correct	2641 ms	1700 KB	Output is correct
9	Correct	3 ms	1528 KB	Output is correct
10	Correct	403 ms	1716 KB	Output is correct
11	Correct	20 ms	21692 KB	Output is correct
12	Correct	2494 ms	21708 KB	Output is correct
13	Correct	1874 ms	1580 KB	Output is correct
14	Correct	2416 ms	21700 KB	Output is correct
15	Correct	3 ms	1528 KB	Output is correct
16	Correct	2419 ms	21756 KB	Output is correct
17	Correct	3 ms	1528 KB	Output is correct
18	Correct	2434 ms	21880 KB	Output is correct
19	Correct	1973 ms	1708 KB	Output is correct
20	Correct	120 ms	21624 KB	Output is correct
21	Correct	854 ms	21768 KB	Output is correct
22	Correct	1977 ms	1716 KB	Output is correct
23	Correct	200 ms	22904 KB	Output is correct
24	Correct	2041 ms	1728 KB	Output is correct
25	Correct	70 ms	22776 KB	Output is correct
26	Correct	2446 ms	22264 KB	Output is correct
27	Correct	2491 ms	22832 KB	Output is correct
28	Correct	2439 ms	21980 KB	Output is correct
29	Correct	2861 ms	22764 KB	Output is correct
30	Correct	2463 ms	22776 KB	Output is correct
31	Correct	2507 ms	23160 KB	Output is correct
32	Correct	2566 ms	22720 KB	Output is correct
33	Correct	2604 ms	23092 KB	Output is correct
34	Correct	2583 ms	23016 KB	Output is correct
35	Correct	2268 ms	12016 KB	Output is correct
36	Correct	2289 ms	12024 KB	Output is correct
37	Correct	2431 ms	12024 KB	Output is correct
38	Correct	2009 ms	6680 KB	Output is correct
39	Correct	2041 ms	6668 KB	Output is correct
40	Correct	60 ms	23288 KB	Output is correct
41	Correct	2083 ms	6648 KB	Output is correct
42	Correct	65 ms	23428 KB	Output is correct
43	Correct	65 ms	23344 KB	Output is correct
44	Correct	1305 ms	1616 KB	Output is correct
45	Execution timed out	3054 ms	302584 KB	Time limit exceeded
46	Halted	0 ms	0 KB	-