답안 #914308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914308	2024-01-21T15:11:02 Z	dsyz	Paths (BOI18_paths)	C++17	100 / 100	1688 ms	174164 KB

paths

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (300005)
ll N,M,K;
vector<ll> v[MAXN];
ll colour[MAXN], dp[MAXN][(1ll<<6) + 1];
bool visited[MAXN][(1ll<<6) + 1];
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>M>>K;
	for(ll i = 0;i < N;i++){
		cin>>colour[i];
		dp[i][1ll<<colour[i]] = 1;
	}
	for(ll i = 0;i < M;i++){
		ll a,b;
		cin>>a>>b;
		a--, b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(ll bitmask = 0;bitmask < (1ll<<6);bitmask++){
		for(ll x = 0;x < N;x++){
			for(auto u : v[x]){
				if((bitmask & (1ll<<colour[u])) == 0){
					dp[u][bitmask | (1ll<<colour[u])] += dp[x][bitmask];
				}
			}
		}
	}
	ll ans = 0;
	for(ll bitmask = 0;bitmask < (1ll<<6);bitmask++){
		for(ll x = 0;x < N;x++){
			ans += dp[x][bitmask];
		}
	}
	cout<<ans - N<<'\n';
}

Subtask #1

23.0 / 23.0

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

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	203 ms	22368 KB	Output is correct
2	Correct	174 ms	20256 KB	Output is correct
3	Correct	1625 ms	173648 KB	Output is correct
4	Correct	359 ms	35616 KB	Output is correct
5	Correct	265 ms	35668 KB	Output is correct
6	Correct	1095 ms	122300 KB	Output is correct
7	Correct	1589 ms	173400 KB	Output is correct
8	Correct	1645 ms	173976 KB	Output is correct

Subtask #3

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12888 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	3 ms	12892 KB	Output is correct
4	Correct	2 ms	12892 KB	Output is correct
5	Correct	3 ms	12892 KB	Output is correct
6	Correct	3 ms	12892 KB	Output is correct
7	Correct	2 ms	12892 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	2 ms	12892 KB	Output is correct
10	Correct	3 ms	12892 KB	Output is correct
11	Correct	203 ms	22368 KB	Output is correct
12	Correct	174 ms	20256 KB	Output is correct
13	Correct	1625 ms	173648 KB	Output is correct
14	Correct	359 ms	35616 KB	Output is correct
15	Correct	265 ms	35668 KB	Output is correct
16	Correct	1095 ms	122300 KB	Output is correct
17	Correct	1589 ms	173400 KB	Output is correct
18	Correct	1645 ms	173976 KB	Output is correct
19	Correct	197 ms	22368 KB	Output is correct
20	Correct	198 ms	20256 KB	Output is correct
21	Correct	1620 ms	173436 KB	Output is correct
22	Correct	395 ms	35616 KB	Output is correct
23	Correct	279 ms	35412 KB	Output is correct
24	Correct	1130 ms	122328 KB	Output is correct
25	Correct	1675 ms	173436 KB	Output is correct
26	Correct	1688 ms	174164 KB	Output is correct
27	Correct	188 ms	20276 KB	Output is correct
28	Correct	277 ms	25684 KB	Output is correct
29	Correct	1587 ms	173440 KB	Output is correct
30	Correct	992 ms	97608 KB	Output is correct
31	Correct	1022 ms	97724 KB	Output is correct
32	Correct	1564 ms	173452 KB	Output is correct
33	Correct	3 ms	12892 KB	Output is correct
34	Correct	3 ms	12892 KB	Output is correct
35	Correct	3 ms	12892 KB	Output is correct
36	Correct	2 ms	12892 KB	Output is correct
37	Correct	2 ms	12892 KB	Output is correct
38	Correct	3 ms	12892 KB	Output is correct
39	Correct	3 ms	13132 KB	Output is correct
40	Correct	2 ms	12892 KB	Output is correct
41	Correct	2 ms	12892 KB	Output is correct
42	Correct	3 ms	12892 KB	Output is correct

Subtask #4

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12892 KB	Output is correct
2	Correct	67 ms	16028 KB	Output is correct
3	Correct	59 ms	15964 KB	Output is correct
4	Correct	348 ms	69268 KB	Output is correct
5	Correct	247 ms	69604 KB	Output is correct
6	Correct	325 ms	69272 KB	Output is correct
7	Correct	66 ms	15964 KB	Output is correct
8	Correct	332 ms	69068 KB	Output is correct
9	Correct	211 ms	69584 KB	Output is correct
10	Correct	307 ms	69836 KB	Output is correct
11	Correct	156 ms	41420 KB	Output is correct
12	Correct	237 ms	54340 KB	Output is correct
13	Correct	162 ms	41804 KB	Output is correct
14	Correct	383 ms	69280 KB	Output is correct
15	Correct	343 ms	69384 KB	Output is correct
16	Correct	3 ms	12892 KB	Output is correct
17	Correct	3 ms	12892 KB	Output is correct
18	Correct	3 ms	13128 KB	Output is correct
19	Correct	3 ms	12892 KB	Output is correct
20	Correct	3 ms	12892 KB	Output is correct
21	Correct	3 ms	12892 KB	Output is correct
22	Correct	3 ms	12892 KB	Output is correct
23	Correct	3 ms	12892 KB	Output is correct
24	Correct	2 ms	12892 KB	Output is correct
25	Correct	3 ms	12892 KB	Output is correct