답안 #226972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226972	2020-04-25T19:05:11 Z	anubhavdhar	Paths (BOI18_paths)	C++14	100 / 100	798 ms	60408 KB

paths

#include<bits/stdc++.h>

#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define all(x) (x).begin(),(x).end()

using namespace std;

const short int __PRECISION = 10;

const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 2e5+5;
const ll ROOTN = 320;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

int main()
{
	/*
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	*/


	int N,M,K;
	int i,j,k,mask;
	ll ans = 0;

	cin>>N>>M>>K;

	vi g[N+1];
	ll dp[N+1][(1<<K)],col[N+1];

	FORe(i,N)
	{
		cin>>j;
		col[i] = j-1;
	}

	FOR(i,M)
	{
		cin>>j>>k;
		if(col[j] != col[k])
		{
			g[j].pb(k);
			g[k].pb(j);
		}
	}

	FOR(i,N+1)
		FOR(mask,(1<<K))
			dp[i][mask] = 0;

	FORe(i,N)
		dp[i][(1<<col[i])] = 1;
	
	FOR(mask,(1<<K))
		FORe(i,N)
			if(mask&(1<<col[i]))
				for(ll b : g[i])
					if(((1<<col[b])&(mask)) == 0)
						dp[b][(mask | (1<<col[b]))] +=	dp[i][mask];

	FORe(i,N)
		FOR(mask,(1<<K))
		{
			if(__builtin_popcount(mask) > 1)
				ans += dp[i][mask];
			//cout<<"dp["<<i<<"]["<<(bitset<5>(mask).to_string())<<"] = "<<dp[i][mask]<<endl;
		}

	cout<<ans;
	return 0;
}

Subtask #1
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	256 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	256 KB	Output is correct
5	Correct	5 ms	256 KB	Output is correct
6	Correct	4 ms	256 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	5 ms	256 KB	Output is correct
10	Correct	4 ms	256 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	254 ms	9080 KB	Output is correct
2	Correct	210 ms	6520 KB	Output is correct
3	Correct	575 ms	40652 KB	Output is correct
4	Correct	278 ms	9720 KB	Output is correct
5	Correct	247 ms	5240 KB	Output is correct
6	Correct	452 ms	29892 KB	Output is correct
7	Correct	707 ms	40700 KB	Output is correct
8	Correct	599 ms	41208 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	256 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	256 KB	Output is correct
5	Correct	5 ms	256 KB	Output is correct
6	Correct	4 ms	256 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	5 ms	256 KB	Output is correct
10	Correct	4 ms	256 KB	Output is correct
11	Correct	254 ms	9080 KB	Output is correct
12	Correct	210 ms	6520 KB	Output is correct
13	Correct	575 ms	40652 KB	Output is correct
14	Correct	278 ms	9720 KB	Output is correct
15	Correct	247 ms	5240 KB	Output is correct
16	Correct	452 ms	29892 KB	Output is correct
17	Correct	707 ms	40700 KB	Output is correct
18	Correct	599 ms	41208 KB	Output is correct
19	Correct	249 ms	9180 KB	Output is correct
20	Correct	210 ms	6520 KB	Output is correct
21	Correct	647 ms	40784 KB	Output is correct
22	Correct	321 ms	9848 KB	Output is correct
23	Correct	244 ms	5284 KB	Output is correct
24	Correct	450 ms	29808 KB	Output is correct
25	Correct	604 ms	40756 KB	Output is correct
26	Correct	590 ms	41336 KB	Output is correct
27	Correct	225 ms	9768 KB	Output is correct
28	Correct	271 ms	9848 KB	Output is correct
29	Correct	784 ms	60340 KB	Output is correct
30	Correct	530 ms	34792 KB	Output is correct
31	Correct	663 ms	35436 KB	Output is correct
32	Correct	798 ms	60408 KB	Output is correct
33	Correct	5 ms	256 KB	Output is correct
34	Correct	6 ms	384 KB	Output is correct
35	Correct	5 ms	256 KB	Output is correct
36	Correct	5 ms	256 KB	Output is correct
37	Correct	5 ms	256 KB	Output is correct
38	Correct	5 ms	384 KB	Output is correct
39	Correct	5 ms	256 KB	Output is correct
40	Correct	4 ms	384 KB	Output is correct
41	Correct	4 ms	256 KB	Output is correct
42	Correct	4 ms	256 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	256 KB	Output is correct
2	Correct	88 ms	3320 KB	Output is correct
3	Correct	74 ms	3192 KB	Output is correct
4	Correct	180 ms	13644 KB	Output is correct
5	Correct	140 ms	13660 KB	Output is correct
6	Correct	273 ms	32760 KB	Output is correct
7	Correct	75 ms	3192 KB	Output is correct
8	Correct	209 ms	20124 KB	Output is correct
9	Correct	168 ms	20204 KB	Output is correct
10	Correct	200 ms	21072 KB	Output is correct
11	Correct	171 ms	17784 KB	Output is correct
12	Correct	242 ms	25960 KB	Output is correct
13	Correct	172 ms	18024 KB	Output is correct
14	Correct	306 ms	32888 KB	Output is correct
15	Correct	291 ms	32760 KB	Output is correct
16	Correct	5 ms	384 KB	Output is correct
17	Correct	4 ms	384 KB	Output is correct
18	Correct	4 ms	384 KB	Output is correct
19	Correct	5 ms	256 KB	Output is correct
20	Correct	4 ms	256 KB	Output is correct
21	Correct	5 ms	384 KB	Output is correct
22	Correct	5 ms	384 KB	Output is correct
23	Correct	5 ms	384 KB	Output is correct
24	Correct	5 ms	256 KB	Output is correct
25	Correct	4 ms	256 KB	Output is correct

답안 #226972

Compilation message

Subtask #1 23.0 / 23.0

Subtask #2 20.0 / 20.0

Subtask #3 27.0 / 27.0

Subtask #4 30.0 / 30.0

Subtask #1
23.0 / 23.0

Subtask #2
20.0 / 20.0

Subtask #3
27.0 / 27.0

Subtask #4
30.0 / 30.0