oj.uz

Submission #121012

# Submission time Handle Problem Language Result Execution time Memory
121012 2019-06-26T02:16:58 Z IOrtroiii Paths (BOI18_paths) C++14
53 / 100
 357 ms 33132 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int N = 100100;
const int K = 5;

int n, m, k;
int a[N];
vector<int> g[N];
ll f[N][1 << K];

int main() {
   scanf("%d %d %d", &n, &m, &k);
   for (int i = 1; i <= n; ++i) {
      scanf("%d", a + i);
      --a[i];
   }
   for (int i = 1; i <= m; ++i) {
      int u, v;
      scanf("%d %d", &u, &v);
      g[u].push_back(v);
      g[v].push_back(u);
   }
   for (int i = 1; i <= n; ++i) {
      f[i][1 << a[i]] = 1ll;
   }
   ll ans = 0;
   for (int mask = 1; mask < (1 << k); ++mask) {
      for (int i = 1; i <= n; ++i) {
         ans += f[i][mask];
         for (int j : g[i]) {
            if (!(mask & (1 << a[j]))) {
               f[j][mask | (1 << a[j])] += f[i][mask];
            }
         }
      }
   }
   printf("%lld\n", ans - n);
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:15:9: 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:17:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", a + i);
       ~~~~~^~~~~~~~~~~~~
paths.cpp:22:12: 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 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2748 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 4 ms 2688 KB Output is correct
10 Correct 5 ms 2688 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 10488 KB Output is correct
2 Correct 87 ms 8696 KB Output is correct
3 Incorrect 14 ms 3456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2748 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 4 ms 2688 KB Output is correct
10 Correct 5 ms 2688 KB Output is correct
11 Correct 106 ms 10488 KB Output is correct
12 Correct 87 ms 8696 KB Output is correct
13 Incorrect 14 ms 3456 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 55 ms 4600 KB Output is correct
3 Correct 30 ms 4608 KB Output is correct
4 Correct 124 ms 32240 KB Output is correct
5 Correct 249 ms 33132 KB Output is correct
6 Correct 276 ms 32376 KB Output is correct
7 Correct 38 ms 4600 KB Output is correct
8 Correct 192 ms 32376 KB Output is correct
9 Correct 135 ms 33008 KB Output is correct
10 Correct 160 ms 32876 KB Output is correct
11 Correct 135 ms 18428 KB Output is correct
12 Correct 173 ms 25908 KB Output is correct
13 Correct 136 ms 18508 KB Output is correct
14 Correct 297 ms 32348 KB Output is correct
15 Correct 357 ms 32504 KB Output is correct
16 Correct 4 ms 2688 KB Output is correct
17 Correct 4 ms 2688 KB Output is correct
18 Correct 4 ms 2688 KB Output is correct
19 Correct 4 ms 2688 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 4 ms 2688 KB Output is correct
22 Correct 4 ms 2816 KB Output is correct
23 Correct 4 ms 2688 KB Output is correct
24 Correct 4 ms 2688 KB Output is correct
25 Correct 4 ms 2688 KB Output is correct