답안 #914309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914309	2024-01-21T15:12:24 Z	dsyz	Paths (BOI18_paths)	C++17	100 / 100	956 ms	96056 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<<5];
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];
		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<<5);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<<5);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	2 ms	10844 KB	Output is correct
2	Correct	2 ms	10944 KB	Output is correct
3	Correct	2 ms	10844 KB	Output is correct
4	Correct	2 ms	10844 KB	Output is correct
5	Correct	2 ms	10844 KB	Output is correct
6	Correct	3 ms	10844 KB	Output is correct
7	Correct	2 ms	10844 KB	Output is correct
8	Correct	2 ms	10940 KB	Output is correct
9	Correct	2 ms	10840 KB	Output is correct
10	Correct	3 ms	10844 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	124 ms	20356 KB	Output is correct
2	Correct	101 ms	20304 KB	Output is correct
3	Correct	858 ms	95500 KB	Output is correct
4	Correct	212 ms	27220 KB	Output is correct
5	Correct	192 ms	27220 KB	Output is correct
6	Correct	588 ms	71152 KB	Output is correct
7	Correct	904 ms	95380 KB	Output is correct
8	Correct	925 ms	96008 KB	Output is correct

Subtask #3

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10844 KB	Output is correct
2	Correct	2 ms	10944 KB	Output is correct
3	Correct	2 ms	10844 KB	Output is correct
4	Correct	2 ms	10844 KB	Output is correct
5	Correct	2 ms	10844 KB	Output is correct
6	Correct	3 ms	10844 KB	Output is correct
7	Correct	2 ms	10844 KB	Output is correct
8	Correct	2 ms	10940 KB	Output is correct
9	Correct	2 ms	10840 KB	Output is correct
10	Correct	3 ms	10844 KB	Output is correct
11	Correct	124 ms	20356 KB	Output is correct
12	Correct	101 ms	20304 KB	Output is correct
13	Correct	858 ms	95500 KB	Output is correct
14	Correct	212 ms	27220 KB	Output is correct
15	Correct	192 ms	27220 KB	Output is correct
16	Correct	588 ms	71152 KB	Output is correct
17	Correct	904 ms	95380 KB	Output is correct
18	Correct	925 ms	96008 KB	Output is correct
19	Correct	114 ms	20168 KB	Output is correct
20	Correct	101 ms	20312 KB	Output is correct
21	Correct	872 ms	95568 KB	Output is correct
22	Correct	200 ms	27220 KB	Output is correct
23	Correct	176 ms	27728 KB	Output is correct
24	Correct	603 ms	71104 KB	Output is correct
25	Correct	956 ms	95328 KB	Output is correct
26	Correct	877 ms	96056 KB	Output is correct
27	Correct	111 ms	20052 KB	Output is correct
28	Correct	149 ms	21588 KB	Output is correct
29	Correct	920 ms	95504 KB	Output is correct
30	Correct	558 ms	58752 KB	Output is correct
31	Correct	554 ms	58816 KB	Output is correct
32	Correct	930 ms	95572 KB	Output is correct
33	Correct	2 ms	10844 KB	Output is correct
34	Correct	2 ms	10844 KB	Output is correct
35	Correct	2 ms	10844 KB	Output is correct
36	Correct	3 ms	10844 KB	Output is correct
37	Correct	2 ms	10840 KB	Output is correct
38	Correct	3 ms	10844 KB	Output is correct
39	Correct	3 ms	10844 KB	Output is correct
40	Correct	3 ms	10844 KB	Output is correct
41	Correct	3 ms	10844 KB	Output is correct
42	Correct	2 ms	10844 KB	Output is correct

Subtask #4

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10844 KB	Output is correct
2	Correct	39 ms	13236 KB	Output is correct
3	Correct	35 ms	13148 KB	Output is correct
4	Correct	217 ms	41296 KB	Output is correct
5	Correct	155 ms	41680 KB	Output is correct
6	Correct	225 ms	41300 KB	Output is correct
7	Correct	37 ms	13148 KB	Output is correct
8	Correct	204 ms	41292 KB	Output is correct
9	Correct	172 ms	41568 KB	Output is correct
10	Correct	189 ms	41676 KB	Output is correct
11	Correct	99 ms	28064 KB	Output is correct
12	Correct	140 ms	34580 KB	Output is correct
13	Correct	87 ms	28244 KB	Output is correct
14	Correct	210 ms	41300 KB	Output is correct
15	Correct	227 ms	41308 KB	Output is correct
16	Correct	3 ms	10840 KB	Output is correct
17	Correct	3 ms	10844 KB	Output is correct
18	Correct	2 ms	10844 KB	Output is correct
19	Correct	3 ms	10844 KB	Output is correct
20	Correct	2 ms	10844 KB	Output is correct
21	Correct	3 ms	10844 KB	Output is correct
22	Correct	2 ms	10936 KB	Output is correct
23	Correct	2 ms	10840 KB	Output is correct
24	Correct	3 ms	10844 KB	Output is correct
25	Correct	3 ms	10844 KB	Output is correct