oj.uz

Submission #532024

# Submission time Handle Problem Language Result Execution time Memory
532024 2022-03-02T03:57:04 Z hohohaha Paths (BOI18_paths) C++14
100 / 100
 688 ms 100396 KB 
#include<bits/stdc++.h>

using namespace std;

#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' '
#define endl '\n'
#define int long long

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count()); 
const int maxn = 3e5 + 5; 
int n, m, k, ans;
int c[maxn];  
vi g[maxn]; 
int dp[maxn][1 << 5]; 
signed main() { 
//	freopen("Paths.inp", "r", stdin); 
//	freopen("Paths.out", "w", stdout); 
	ios_base::sync_with_stdio(0);
	cin.tie(0); 
	cout.tie(0); 
	cin >> n >> m >> k; 
	fori(i, 1, n) { 
		cin >> c[i]; 
		c[i]--; 
	}
	fori(i, 1, m) { 
		int u, v; cin >> u >> v; 
		g[u].eb(v); 
		g[v].eb(u); 
	}
	fori(i, 1, n) { 
		dp[i][1 << c[i]] = 1; 
	}
	fori(mask, 1, (1 << k) - 1) { 
		fori(i, 1, n) { 
			for(int j: g[i]) { 
				if(!(mask >> c[j] & 1)) { 
					dp[j][mask ^ (1 << c[j])] += dp[i][mask]; 
				}
			}
		}
	}
	fori(i, 1, n) { 
		fori(mask, 1, (1 << k) - 1) { 
			if(__builtin_popcountll(mask) >= 2) ans += dp[i][mask]; 
		}
	}
	cout << ans; 
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7364 KB Output is correct
2 Correct 4 ms 7376 KB Output is correct
3 Correct 3 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 3 ms 7372 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 18668 KB Output is correct
2 Correct 68 ms 16972 KB Output is correct
3 Correct 429 ms 99848 KB Output is correct
4 Correct 130 ms 26496 KB Output is correct
5 Correct 98 ms 26564 KB Output is correct
6 Correct 273 ms 71932 KB Output is correct
7 Correct 410 ms 99784 KB Output is correct
8 Correct 416 ms 100320 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7364 KB Output is correct
2 Correct 4 ms 7376 KB Output is correct
3 Correct 3 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 4 ms 7376 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 3 ms 7372 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct
11 Correct 91 ms 18668 KB Output is correct
12 Correct 68 ms 16972 KB Output is correct
13 Correct 429 ms 99848 KB Output is correct
14 Correct 130 ms 26496 KB Output is correct
15 Correct 98 ms 26564 KB Output is correct
16 Correct 273 ms 71932 KB Output is correct
17 Correct 410 ms 99784 KB Output is correct
18 Correct 416 ms 100320 KB Output is correct
19 Correct 85 ms 18628 KB Output is correct
20 Correct 79 ms 16956 KB Output is correct
21 Correct 410 ms 99860 KB Output is correct
22 Correct 103 ms 26580 KB Output is correct
23 Correct 118 ms 26688 KB Output is correct
24 Correct 264 ms 71872 KB Output is correct
25 Correct 420 ms 99916 KB Output is correct
26 Correct 435 ms 100396 KB Output is correct
27 Correct 100 ms 16960 KB Output is correct
28 Correct 153 ms 20788 KB Output is correct
29 Correct 688 ms 99852 KB Output is correct
30 Correct 400 ms 58800 KB Output is correct
31 Correct 424 ms 58956 KB Output is correct
32 Correct 669 ms 99816 KB Output is correct
33 Correct 4 ms 7376 KB Output is correct
34 Correct 5 ms 7316 KB Output is correct
35 Correct 4 ms 7372 KB Output is correct
36 Correct 4 ms 7372 KB Output is correct
37 Correct 4 ms 7300 KB Output is correct
38 Correct 4 ms 7372 KB Output is correct
39 Correct 4 ms 7372 KB Output is correct
40 Correct 4 ms 7372 KB Output is correct
41 Correct 4 ms 7372 KB Output is correct
42 Correct 4 ms 7272 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 60 ms 10400 KB Output is correct
3 Correct 26 ms 10364 KB Output is correct
4 Correct 98 ms 38056 KB Output is correct
5 Correct 73 ms 38460 KB Output is correct
6 Correct 276 ms 38016 KB Output is correct
7 Correct 40 ms 10328 KB Output is correct
8 Correct 160 ms 37980 KB Output is correct
9 Correct 105 ms 38456 KB Output is correct
10 Correct 127 ms 38136 KB Output is correct
11 Correct 153 ms 24144 KB Output is correct
12 Correct 158 ms 31112 KB Output is correct
13 Correct 145 ms 24180 KB Output is correct
14 Correct 277 ms 38096 KB Output is correct
15 Correct 274 ms 38252 KB Output is correct
16 Correct 4 ms 7372 KB Output is correct
17 Correct 4 ms 7372 KB Output is correct
18 Correct 4 ms 7372 KB Output is correct
19 Correct 5 ms 7328 KB Output is correct
20 Correct 4 ms 7372 KB Output is correct
21 Correct 4 ms 7372 KB Output is correct
22 Correct 4 ms 7372 KB Output is correct
23 Correct 4 ms 7372 KB Output is correct
24 Correct 4 ms 7372 KB Output is correct
25 Correct 5 ms 7316 KB Output is correct