Submission #731645

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
731645	2023-04-27T17:43:17 Z	NintsiChkhaidze	Paths (BOI18_paths)	C++17	53 / 100	105 ms	31548 KB

paths

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

const int N = 1e5 + 5;
ll dp[37][N];
int c[N];
vector <int> v[N];

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n,m,k;
	cin>>n>>m>>k;
	
	for (int i = 1; i <= n; i++){
		cin>>c[i];
		--c[i];
		dp[(1<<c[i])][i] = 1;
	}
	for (int i = 1; i <= m; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	
	for (int mask = 0; mask < (1<<k); mask++){
		for (int i = 1; i <= n; i++){
			if (dp[mask][i] && (mask & (1<<c[i])) > 0) {
				for (int to: v[i]){
					if (!(mask & (1<<c[to]))){
						dp[mask ^ (1<<c[to])][to] += dp[mask][i];
					}
				}
			}
		}
	}
	
	ll ans=0;
	for (int i = 1; i <= n; i++){
		for (int mask = 0; mask < (1<<k); mask++){
			if ((mask & (1<<c[i])) > 0 && __builtin_popcount(mask) > 1)
				ans += dp[mask][i];
		}
	}
	cout<<ans;
}

Subtask #1

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2772 KB	Output is correct
2	Correct	2 ms	2772 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	2 ms	2684 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2680 KB	Output is correct
8	Correct	2 ms	2680 KB	Output is correct
9	Correct	1 ms	2644 KB	Output is correct
10	Correct	2 ms	2688 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	9436 KB	Output is correct
2	Correct	56 ms	8604 KB	Output is correct
3	Runtime error	25 ms	17864 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2772 KB	Output is correct
2	Correct	2 ms	2772 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	2 ms	2684 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2680 KB	Output is correct
8	Correct	2 ms	2680 KB	Output is correct
9	Correct	1 ms	2644 KB	Output is correct
10	Correct	2 ms	2688 KB	Output is correct
11	Correct	71 ms	9436 KB	Output is correct
12	Correct	56 ms	8604 KB	Output is correct
13	Runtime error	25 ms	17864 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	36 ms	4816 KB	Output is correct
3	Correct	20 ms	4536 KB	Output is correct
4	Correct	58 ms	12572 KB	Output is correct
5	Correct	47 ms	12684 KB	Output is correct
6	Correct	99 ms	31416 KB	Output is correct
7	Correct	23 ms	4592 KB	Output is correct
8	Correct	79 ms	18920 KB	Output is correct
9	Correct	54 ms	15672 KB	Output is correct
10	Correct	72 ms	14868 KB	Output is correct
11	Correct	65 ms	18072 KB	Output is correct
12	Correct	55 ms	14148 KB	Output is correct
13	Correct	62 ms	14688 KB	Output is correct
14	Correct	105 ms	31340 KB	Output is correct
15	Correct	91 ms	31548 KB	Output is correct
16	Correct	2 ms	2644 KB	Output is correct
17	Correct	2 ms	2684 KB	Output is correct
18	Correct	2 ms	2644 KB	Output is correct
19	Correct	3 ms	2680 KB	Output is correct
20	Correct	2 ms	2688 KB	Output is correct
21	Correct	2 ms	2680 KB	Output is correct
22	Correct	2 ms	2684 KB	Output is correct
23	Correct	2 ms	2684 KB	Output is correct
24	Correct	2 ms	2644 KB	Output is correct
25	Correct	2 ms	2644 KB	Output is correct