Submission #343557

#	Time	Username	Problem	Language	Result	Execution time	Memory
343557		parsabahrami	Paths (BOI18_paths)	C++17	100 / 100	451 ms	56684 KiB

paths

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
 
const int N = 3e5 + 10;
ll dp[40][N]; int n, m, k, C[N];
vector<int> adj[N];
 
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &C[i]), C[i]--;
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) dp[1 << C[i]][i] = 1;
    for (int i = 0; i < 1 << k; i++) {
        for (int j = 1; j <= n; j++) {
            if ((i & (1 << C[j])) == 0) continue;
            for (int u : adj[j]) dp[i][j] += dp[i ^ (1 << C[j])][u];
        }
    }
    ll res = 0;
    for (int i = 1; i <= n; i++) for (int j = 0; j < 1 << k; j++) res += dp[j][i];
    printf("%lld\n", res - n);
    return 0;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
paths.cpp:18:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     for (int i = 1; i <= n; i++) scanf("%d", &C[i]), C[i]--;
      |                                  ~~~~~^~~~~~~~~~~~~
paths.cpp:20:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30