| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 100155 | 2019-03-09T15:59:29 Z | tushar_2658 | Paths (BOI18_paths) | C++14 | 708 ms | 172544 KB |
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int maxn = 3e5 + 5;
int arr[maxn];
vector<int> edges[maxn];
int n, m, k;
ll dp[1 << 6][maxn];
ll call(int mask, int node){
if(dp[mask][node] != -1)return dp[mask][node];
int ans = 1;
for(auto i : edges[node]){
if((mask >> arr[i]) & 1)continue;
else {
ans += call(mask ^ (1 << arr[i]), i);
}
}return dp[mask][node] = ans;
}
int main(){
scanf("%d %d %d", &n, &m, &k);
for(int i=1; i<=n; i++){
scanf("%d", &arr[i]);
//--arr[i];
}
for(int i=1; i<=m; i++){
int x, y;
scanf("%d %d", &x, &y);
edges[x].emplace_back(y);
edges[y].emplace_back(x);
}
memset(dp, -1, sizeof dp);
ll ans = 0, mask = 0;
for(int i=1; i<=n; i++){
ans += call((mask ^ (1 << arr[i])), i);
}cout<<ans-n<<endl;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 130 ms | 157788 KB | Output is correct |
| 2 | Correct | 124 ms | 157688 KB | Output is correct |
| 3 | Correct | 123 ms | 157660 KB | Output is correct |
| 4 | Correct | 122 ms | 157688 KB | Output is correct |
| 5 | Correct | 125 ms | 157660 KB | Output is correct |
| 6 | Correct | 127 ms | 157816 KB | Output is correct |
| 7 | Correct | 128 ms | 157732 KB | Output is correct |
| 8 | Correct | 140 ms | 157604 KB | Output is correct |
| 9 | Correct | 125 ms | 157600 KB | Output is correct |
| 10 | Correct | 118 ms | 157688 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 226 ms | 161448 KB | Output is correct |
| 2 | Correct | 213 ms | 161168 KB | Output is correct |
| 3 | Correct | 614 ms | 167432 KB | Output is correct |
| 4 | Correct | 296 ms | 162224 KB | Output is correct |
| 5 | Correct | 321 ms | 162168 KB | Output is correct |
| 6 | Correct | 420 ms | 165600 KB | Output is correct |
| 7 | Correct | 561 ms | 171784 KB | Output is correct |
| 8 | Correct | 528 ms | 172544 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 130 ms | 157788 KB | Output is correct |
| 2 | Correct | 124 ms | 157688 KB | Output is correct |
| 3 | Correct | 123 ms | 157660 KB | Output is correct |
| 4 | Correct | 122 ms | 157688 KB | Output is correct |
| 5 | Correct | 125 ms | 157660 KB | Output is correct |
| 6 | Correct | 127 ms | 157816 KB | Output is correct |
| 7 | Correct | 128 ms | 157732 KB | Output is correct |
| 8 | Correct | 140 ms | 157604 KB | Output is correct |
| 9 | Correct | 125 ms | 157600 KB | Output is correct |
| 10 | Correct | 118 ms | 157688 KB | Output is correct |
| 11 | Correct | 226 ms | 161448 KB | Output is correct |
| 12 | Correct | 213 ms | 161168 KB | Output is correct |
| 13 | Correct | 614 ms | 167432 KB | Output is correct |
| 14 | Correct | 296 ms | 162224 KB | Output is correct |
| 15 | Correct | 321 ms | 162168 KB | Output is correct |
| 16 | Correct | 420 ms | 165600 KB | Output is correct |
| 17 | Correct | 561 ms | 171784 KB | Output is correct |
| 18 | Correct | 528 ms | 172544 KB | Output is correct |
| 19 | Correct | 244 ms | 164232 KB | Output is correct |
| 20 | Correct | 217 ms | 163448 KB | Output is correct |
| 21 | Correct | 586 ms | 171768 KB | Output is correct |
| 22 | Correct | 313 ms | 165672 KB | Output is correct |
| 23 | Correct | 296 ms | 165708 KB | Output is correct |
| 24 | Correct | 446 ms | 169784 KB | Output is correct |
| 25 | Correct | 617 ms | 171764 KB | Output is correct |
| 26 | Correct | 576 ms | 172408 KB | Output is correct |
| 27 | Correct | 223 ms | 163448 KB | Output is correct |
| 28 | Correct | 299 ms | 164984 KB | Output is correct |
| 29 | Correct | 708 ms | 171880 KB | Output is correct |
| 30 | Correct | 562 ms | 168372 KB | Output is correct |
| 31 | Correct | 558 ms | 168148 KB | Output is correct |
| 32 | Correct | 678 ms | 171896 KB | Output is correct |
| 33 | Correct | 123 ms | 157652 KB | Output is correct |
| 34 | Correct | 127 ms | 157628 KB | Output is correct |
| 35 | Correct | 113 ms | 157692 KB | Output is correct |
| 36 | Correct | 116 ms | 157696 KB | Output is correct |
| 37 | Correct | 126 ms | 157652 KB | Output is correct |
| 38 | Correct | 122 ms | 157732 KB | Output is correct |
| 39 | Correct | 128 ms | 157728 KB | Output is correct |
| 40 | Correct | 122 ms | 157788 KB | Output is correct |
| 41 | Correct | 121 ms | 157688 KB | Output is correct |
| 42 | Correct | 130 ms | 157656 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 112 ms | 157688 KB | Output is correct |
| 2 | Correct | 162 ms | 158868 KB | Output is correct |
| 3 | Correct | 148 ms | 159480 KB | Output is correct |
| 4 | Correct | 222 ms | 162184 KB | Output is correct |
| 5 | Correct | 177 ms | 162928 KB | Output is correct |
| 6 | Correct | 235 ms | 162328 KB | Output is correct |
| 7 | Correct | 143 ms | 159452 KB | Output is correct |
| 8 | Correct | 228 ms | 162296 KB | Output is correct |
| 9 | Correct | 200 ms | 163016 KB | Output is correct |
| 10 | Correct | 263 ms | 162840 KB | Output is correct |
| 11 | Correct | 200 ms | 160908 KB | Output is correct |
| 12 | Correct | 187 ms | 162032 KB | Output is correct |
| 13 | Correct | 219 ms | 161008 KB | Output is correct |
| 14 | Correct | 277 ms | 162168 KB | Output is correct |
| 15 | Correct | 277 ms | 162440 KB | Output is correct |
| 16 | Correct | 132 ms | 157688 KB | Output is correct |
| 17 | Correct | 121 ms | 157656 KB | Output is correct |
| 18 | Correct | 121 ms | 157660 KB | Output is correct |
| 19 | Correct | 134 ms | 157724 KB | Output is correct |
| 20 | Correct | 125 ms | 157688 KB | Output is correct |
| 21 | Correct | 125 ms | 157812 KB | Output is correct |
| 22 | Correct | 121 ms | 157824 KB | Output is correct |
| 23 | Correct | 114 ms | 157664 KB | Output is correct |
| 24 | Correct | 117 ms | 157712 KB | Output is correct |
| 25 | Correct | 129 ms | 157668 KB | Output is correct |