Submission #80674

#	Time	Username	Problem	Language	Result	Execution time	Memory
80674		FutymyClone	Paths (BOI18_paths)	C++14	100 / 100	661 ms	173388 KiB

paths

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

int n, m, k, a[N];
long long dp[N][32];
vector <int> g[N];

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &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++) dp[i][1 << (a[i] - 1)] = 1;
    for (int i = 1; i < 32; i++) {
        for (int j = 1; j <= n; j++) {
            if (dp[j][i]) {
                for (auto v: g[j]) {
                    if (i & (1 << (a[v] - 1))) continue;
                    dp[v][i | (1 << (a[v] - 1))] += dp[j][i];
                }
            }
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j < 32; j++) ans += dp[i][j];
    printf("%lld", ans - n);
    return 0;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:12:10: 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:13:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
                                  ~~~~~^~~~~~~~~~~~~
paths.cpp:16:14: 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