답안 #69777 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69777	2018-08-21T13:22:24 Z	MrTEK	Paths (BOI18_paths)	C++14	100 / 100	1463 ms	542216 KB

paths

#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left isc+isc
#define right isc+isc+1
#define mid (l+r)/2
#define FAfi_IO ios_base::sync_with_fidio(false);
#define escl '\n'

typedef long long int ll;

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 3e5 + 5;
const int M = 5;
const int SQ = 350;
const int MOD = 998244353;

typedef long long int lli;
typedef pair<int,int> pii;

vector <int> ed[N];

int n,m,k,col[N];
long long ans,dp[N][1 << 5][6];

int main() {
	scanf("%d %d %d",&n,&m,&k);
	for (int i = 1 ; i <= n ; i++) {
		scanf("%d",&col[i]);
		col[i]--;
	}
	for (int i = 1 ; i <= m ; i++) {
		int u,v;
		scanf("%d %d",&u,&v);
		ed[u].pb(v);
		ed[v].pb(u);
	}

	for (int i = 1 ; i <= n ; i++)
		dp[i][1 << col[i]][0] = 1;

	for (int i = 1 ; i < k ; i++) {
		for (int cur = 1 ; cur <= n ; cur++) {
			for (auto nxt : ed[cur]) {
				for (int mask = 0 ; mask < (1 << k) ; mask++) {
					if ((mask & (1 << col[cur])) == 0)
						dp[cur][mask + (1 << col[cur])][i] += dp[nxt][mask][i - 1];
				}
			}
		}
	}

	for (int i = 1 ; i < k ; i++)
		for (int cur = 1 ; cur <= n ; cur++)
			for (int mask = 0 ; mask < (1 << k) ; mask++)
				ans += dp[cur][mask][i];
	printf("%lld\n",ans);
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
paths.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&col[i]);
   ~~~~~^~~~~~~~~~~~~~
paths.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

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

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	164 ms	18916 KB	Output is correct
2	Correct	127 ms	18916 KB	Output is correct
3	Correct	987 ms	472104 KB	Output is correct
4	Correct	232 ms	472104 KB	Output is correct
5	Correct	191 ms	472104 KB	Output is correct
6	Correct	666 ms	472104 KB	Output is correct
7	Correct	917 ms	487724 KB	Output is correct
8	Correct	917 ms	492848 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	7416 KB	Output is correct
2	Correct	12 ms	7656 KB	Output is correct
3	Correct	9 ms	7692 KB	Output is correct
4	Correct	9 ms	7692 KB	Output is correct
5	Correct	10 ms	7692 KB	Output is correct
6	Correct	9 ms	7692 KB	Output is correct
7	Correct	8 ms	7692 KB	Output is correct
8	Correct	10 ms	7692 KB	Output is correct
9	Correct	10 ms	7692 KB	Output is correct
10	Correct	8 ms	7692 KB	Output is correct
11	Correct	164 ms	18916 KB	Output is correct
12	Correct	127 ms	18916 KB	Output is correct
13	Correct	987 ms	472104 KB	Output is correct
14	Correct	232 ms	472104 KB	Output is correct
15	Correct	191 ms	472104 KB	Output is correct
16	Correct	666 ms	472104 KB	Output is correct
17	Correct	917 ms	487724 KB	Output is correct
18	Correct	917 ms	492848 KB	Output is correct
19	Correct	160 ms	492848 KB	Output is correct
20	Correct	106 ms	492848 KB	Output is correct
21	Correct	934 ms	501720 KB	Output is correct
22	Correct	305 ms	501720 KB	Output is correct
23	Correct	247 ms	501720 KB	Output is correct
24	Correct	627 ms	501720 KB	Output is correct
25	Correct	938 ms	516836 KB	Output is correct
26	Correct	911 ms	521872 KB	Output is correct
27	Correct	204 ms	521872 KB	Output is correct
28	Correct	340 ms	521872 KB	Output is correct
29	Correct	1317 ms	530544 KB	Output is correct
30	Correct	930 ms	530544 KB	Output is correct
31	Correct	1047 ms	530544 KB	Output is correct
32	Correct	1463 ms	542216 KB	Output is correct
33	Correct	10 ms	542216 KB	Output is correct
34	Correct	9 ms	542216 KB	Output is correct
35	Correct	9 ms	542216 KB	Output is correct
36	Correct	9 ms	542216 KB	Output is correct
37	Correct	11 ms	542216 KB	Output is correct
38	Correct	11 ms	542216 KB	Output is correct
39	Correct	11 ms	542216 KB	Output is correct
40	Correct	10 ms	542216 KB	Output is correct
41	Correct	8 ms	542216 KB	Output is correct
42	Correct	9 ms	542216 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	542216 KB	Output is correct
2	Correct	103 ms	542216 KB	Output is correct
3	Correct	39 ms	542216 KB	Output is correct
4	Correct	299 ms	542216 KB	Output is correct
5	Correct	238 ms	542216 KB	Output is correct
6	Correct	701 ms	542216 KB	Output is correct
7	Correct	62 ms	542216 KB	Output is correct
8	Correct	404 ms	542216 KB	Output is correct
9	Correct	380 ms	542216 KB	Output is correct
10	Correct	387 ms	542216 KB	Output is correct
11	Correct	400 ms	542216 KB	Output is correct
12	Correct	451 ms	542216 KB	Output is correct
13	Correct	412 ms	542216 KB	Output is correct
14	Correct	627 ms	542216 KB	Output is correct
15	Correct	644 ms	542216 KB	Output is correct
16	Correct	9 ms	542216 KB	Output is correct
17	Correct	10 ms	542216 KB	Output is correct
18	Correct	8 ms	542216 KB	Output is correct
19	Correct	9 ms	542216 KB	Output is correct
20	Correct	9 ms	542216 KB	Output is correct
21	Correct	8 ms	542216 KB	Output is correct
22	Correct	11 ms	542216 KB	Output is correct
23	Correct	10 ms	542216 KB	Output is correct
24	Correct	8 ms	542216 KB	Output is correct
25	Correct	8 ms	542216 KB	Output is correct

답안 #69777

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