Submission #121013

#	Time	Username	Problem	Language	Result	Execution time	Memory
121013		IOrtroiii	Paths (BOI18_paths)	C++14	100 / 100	1215 ms	97400 KiB

paths

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int N = 300300;
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])) {
               continue;
            }
            f[j][mask | (1 << a[j])] += f[i][mask];
         }
      }
   }
   printf("%lld\n", ans - n);
}

Compilation message (stderr)

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 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30