| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 106403 | 2019-04-18T10:42:10 Z | eriksuenderhauf | Paths (BOI18_paths) | C++11 | 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
| # | 결과 | 실행 시간 | 메모리 | 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 |
| # | 결과 | 실행 시간 | 메모리 | 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 |
| # | 결과 | 실행 시간 | 메모리 | 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 |
| # | 결과 | 실행 시간 | 메모리 | 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 |