답안 #825435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
825435	2023-08-14T20:12:49 Z	QwertyPi	Paths (BOI18_paths)	C++14	53 / 100	291 ms	33760 KB

paths

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 1e5 + 11;

int a[MAXN];
int dp[MAXN][1 << 5];
vector<int> G[MAXN];
struct edge{
	int u, v;
};

vector<edge> E;
int32_t main(){
	int n, m, k; cin >> n >> m >> k;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) a[i]--;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v; u--; v--;
		G[u].push_back(v); G[v].push_back(u);
	}
	for(int i = 0; i < n; i++){
		dp[i][1 << a[i]] = 1;
	}

	for(int mask = 0; mask < (1 << k); mask++){
		for(int j = 0; j < k; j++){
			if((1 << j) & mask){
				for(int i = 0; i < n; i++){
					for(auto u : G[i]){
						if(a[u] != j) continue;
						dp[u][mask] += dp[i][mask - (1 << j)];
					}
				}
			}
		}
	}

	int ans = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < (1 << k); j++){
			ans += dp[i][j];
		}
	}
	cout << ans - n << endl;
}

Subtask #1

23.0 / 23.0

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

Subtask #2

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	160 ms	13960 KB	Output is correct
2	Correct	116 ms	12252 KB	Output is correct
3	Runtime error	15 ms	7124 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	2 ms	2656 KB	Output is correct
5	Correct	1 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	2 ms	2664 KB	Output is correct
9	Correct	1 ms	2644 KB	Output is correct
10	Correct	1 ms	2644 KB	Output is correct
11	Correct	160 ms	13960 KB	Output is correct
12	Correct	116 ms	12252 KB	Output is correct
13	Runtime error	15 ms	7124 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Subtask #4

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	72 ms	5688 KB	Output is correct
3	Correct	41 ms	5632 KB	Output is correct
4	Correct	121 ms	33232 KB	Output is correct
5	Correct	113 ms	33760 KB	Output is correct
6	Correct	280 ms	33356 KB	Output is correct
7	Correct	53 ms	5660 KB	Output is correct
8	Correct	167 ms	33324 KB	Output is correct
9	Correct	123 ms	33656 KB	Output is correct
10	Correct	159 ms	33492 KB	Output is correct
11	Correct	171 ms	19336 KB	Output is correct
12	Correct	187 ms	26468 KB	Output is correct
13	Correct	180 ms	19464 KB	Output is correct
14	Correct	268 ms	33328 KB	Output is correct
15	Correct	291 ms	33416 KB	Output is correct
16	Correct	1 ms	2644 KB	Output is correct
17	Correct	1 ms	2656 KB	Output is correct
18	Correct	1 ms	2644 KB	Output is correct
19	Correct	1 ms	2660 KB	Output is correct
20	Correct	2 ms	2644 KB	Output is correct
21	Correct	2 ms	2644 KB	Output is correct
22	Correct	1 ms	2644 KB	Output is correct
23	Correct	1 ms	2664 KB	Output is correct
24	Correct	1 ms	2644 KB	Output is correct
25	Correct	1 ms	2644 KB	Output is correct