oj.uz

Submission #106403

# Submission time Handle Problem Language Result Execution time Memory
106403 2019-04-18T10:42:10 Z eriksuenderhauf Paths (BOI18_paths) C++11
100 / 100
 670 ms 115960 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
const double eps = 1e-9;
ll dp[MAXN][40];
int a[MAXN];
vi adj[MAXN];

int main() {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 0; i < n; i++) {
		ni(a[i]); a[i]--;
		dp[i][1<<a[i]] = 1;
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		u--, v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	ll ans = 0;
	for (int i = 1; i < (1 << k); i++) {
		if (__builtin_popcount(i) == 1) continue;
		for (int j = 0; j < n; j++) {
			if (!((i >> a[j]) & 1)) continue;
			for (int u: adj[j])
				dp[j][i] += dp[u][i^(1<<a[j])];
			ans += dp[j][i];
		}
	}
	prl(ans);
	return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:7:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
paths.cpp:43:3: note: in expansion of macro 'ni'
   ni(a[i]); a[i]--;
   ^~
paths.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 15480 KB Output is correct
2 Correct 95 ms 13304 KB Output is correct
3 Correct 490 ms 115448 KB Output is correct
4 Correct 182 ms 24720 KB Output is correct
5 Correct 166 ms 24680 KB Output is correct
6 Correct 321 ms 81896 KB Output is correct
7 Correct 551 ms 115580 KB Output is correct
8 Correct 444 ms 115960 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 9 ms 7420 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 10 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 8 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 185 ms 15480 KB Output is correct
12 Correct 95 ms 13304 KB Output is correct
13 Correct 490 ms 115448 KB Output is correct
14 Correct 182 ms 24720 KB Output is correct
15 Correct 166 ms 24680 KB Output is correct
16 Correct 321 ms 81896 KB Output is correct
17 Correct 551 ms 115580 KB Output is correct
18 Correct 444 ms 115960 KB Output is correct
19 Correct 140 ms 15448 KB Output is correct
20 Correct 80 ms 13396 KB Output is correct
21 Correct 458 ms 115432 KB Output is correct
22 Correct 177 ms 24804 KB Output is correct
23 Correct 155 ms 24676 KB Output is correct
24 Correct 387 ms 82000 KB Output is correct
25 Correct 429 ms 115392 KB Output is correct
26 Correct 511 ms 115888 KB Output is correct
27 Correct 126 ms 13304 KB Output is correct
28 Correct 131 ms 17200 KB Output is correct
29 Correct 670 ms 115476 KB Output is correct
30 Correct 395 ms 64824 KB Output is correct
31 Correct 441 ms 64804 KB Output is correct
32 Correct 613 ms 115320 KB Output is correct
33 Correct 8 ms 7424 KB Output is correct
34 Correct 9 ms 7424 KB Output is correct
35 Correct 8 ms 7424 KB Output is correct
36 Correct 8 ms 7424 KB Output is correct
37 Correct 8 ms 7396 KB Output is correct
38 Correct 8 ms 7424 KB Output is correct
39 Correct 8 ms 7396 KB Output is correct
40 Correct 8 ms 7424 KB Output is correct
41 Correct 8 ms 7424 KB Output is correct
42 Correct 9 ms 7424 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7424 KB Output is correct
2 Correct 38 ms 9352 KB Output is correct
3 Correct 36 ms 9336 KB Output is correct
4 Correct 150 ms 43256 KB Output is correct
5 Correct 117 ms 43920 KB Output is correct
6 Correct 276 ms 43240 KB Output is correct
7 Correct 36 ms 9336 KB Output is correct
8 Correct 216 ms 43460 KB Output is correct
9 Correct 118 ms 44016 KB Output is correct
10 Correct 143 ms 44020 KB Output is correct
11 Correct 115 ms 26228 KB Output is correct
12 Correct 151 ms 35232 KB Output is correct
13 Correct 98 ms 26368 KB Output is correct
14 Correct 293 ms 43304 KB Output is correct
15 Correct 345 ms 43384 KB Output is correct
16 Correct 9 ms 7424 KB Output is correct
17 Correct 9 ms 7424 KB Output is correct
18 Correct 10 ms 7424 KB Output is correct
19 Correct 9 ms 7424 KB Output is correct
20 Correct 8 ms 7424 KB Output is correct
21 Correct 8 ms 7424 KB Output is correct
22 Correct 10 ms 7424 KB Output is correct
23 Correct 10 ms 7424 KB Output is correct
24 Correct 9 ms 7500 KB Output is correct
25 Correct 10 ms 7424 KB Output is correct