oj.uz

답안 #1098066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1098066 2024-10-09T02:58:18 Z Alihan_8 Paths (BOI18_paths) C++17
100 / 100
 217 ms 70740 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

using i64 = long long;

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, k; cin >> n >> m >> k;
	
	vector <int> c(n);
	
	for ( auto &u: c ){
		cin >> u; --u;
	}
	
	vector <vector<int>> adj(n);
	
	for ( int i = 0; i < m; i++ ){
		int u, v; cin >> u >> v;
		
		--u, --v;
		
		adj[u].pb(v);
		adj[v].pb(u);
	}
	
	const int S = 1 << k;
	
	vector <vector<i64>> dp(n, vector <i64> (S, -1));
	
	auto dfs = [&](auto dfs, int u, int mask) -> i64{
		if ( dp[u][mask] != -1 ) return dp[u][mask];
		
		i64 &ret = dp[u][mask]; ret = 0;
		
		for ( auto &v: adj[u] ){
			if ( mask >> c[v] & 1 ) continue;
			
			ret += dfs(dfs, v, mask | (1 << c[v])) + 1;
		}
		
		return ret;
	};
	
	i64 ans = 0;
	
	for ( int i = 0; i < n; i++ ){
		ans += dfs(dfs, i, 1 << c[i]);
	}
	
	cout << ans;
	
	cout << '\n';
}

Subtask #1
23.0 / 23.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 6960 KB Output is correct
2 Correct 35 ms 6228 KB Output is correct
3 Correct 169 ms 51796 KB Output is correct
4 Correct 57 ms 10756 KB Output is correct
5 Correct 56 ms 10064 KB Output is correct
6 Correct 118 ms 37252 KB Output is correct
7 Correct 176 ms 51960 KB Output is correct
8 Correct 155 ms 52564 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 46 ms 6960 KB Output is correct
12 Correct 35 ms 6228 KB Output is correct
13 Correct 169 ms 51796 KB Output is correct
14 Correct 57 ms 10756 KB Output is correct
15 Correct 56 ms 10064 KB Output is correct
16 Correct 118 ms 37252 KB Output is correct
17 Correct 176 ms 51960 KB Output is correct
18 Correct 155 ms 52564 KB Output is correct
19 Correct 45 ms 6996 KB Output is correct
20 Correct 36 ms 6236 KB Output is correct
21 Correct 165 ms 51796 KB Output is correct
22 Correct 57 ms 10576 KB Output is correct
23 Correct 51 ms 10072 KB Output is correct
24 Correct 113 ms 37432 KB Output is correct
25 Correct 165 ms 51792 KB Output is correct
26 Correct 174 ms 52568 KB Output is correct
27 Correct 46 ms 6112 KB Output is correct
28 Correct 63 ms 8704 KB Output is correct
29 Correct 217 ms 70740 KB Output is correct
30 Correct 146 ms 38860 KB Output is correct
31 Correct 153 ms 38860 KB Output is correct
32 Correct 210 ms 70736 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 344 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 24 ms 2136 KB Output is correct
3 Correct 13 ms 2140 KB Output is correct
4 Correct 41 ms 17480 KB Output is correct
5 Correct 36 ms 18124 KB Output is correct
6 Correct 74 ms 36128 KB Output is correct
7 Correct 16 ms 2132 KB Output is correct
8 Correct 53 ms 23636 KB Output is correct
9 Correct 47 ms 24408 KB Output is correct
10 Correct 44 ms 24264 KB Output is correct
11 Correct 52 ms 19256 KB Output is correct
12 Correct 41 ms 28168 KB Output is correct
13 Correct 49 ms 19144 KB Output is correct
14 Correct 77 ms 36176 KB Output is correct
15 Correct 56 ms 36176 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 600 KB Output is correct