oj.uz

Submission #887674

# Submission time Handle Problem Language Result Execution time Memory
887674 2023-12-15T02:31:25 Z votranngocvy Paths (BOI18_paths) C++14
23 / 100
 177 ms 57940 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;
int n,m,k,a[N];
vector<int>g[N];

namespace sub1 {
    int ans = 0;
    bool vis[10];
    void dfs(int u) {
        vis[a[u]] = true;
        for (auto v: g[u]) {
            if (vis[a[v]]) continue;
            ans++;
            dfs(v);
        }
        vis[a[u]] = false;
    }
    void solve() {
        for (int i = 1; i <= n; i++) dfs(i);
        cout << ans << "\n";
    }
}

namespace sol {
    int dp[N][35];
    void solve() {
        for (int i = 1; i <= n; i++) dp[i][(1 << a[i])] = 1;
        for (int mask = 0; mask < (1 << k); mask++) {
            for (int u = 1; u <= n; u++) {
                if (dp[u][mask] == 0) continue;
                for (auto v: g[u]) {
                    if (mask & (1 << a[v])) continue;
                    dp[v][mask | (1 << a[v])] += dp[u][mask];
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
            for (int mask = 0; mask < (1 << k); mask++)
                if (__builtin_popcount(mask) >= 2) ans += dp[i][mask];
        cout << ans << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 1; i <= m; i++) {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    sol::solve();
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9560 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 2 ms 9560 KB Output is correct
5 Correct 2 ms 9392 KB Output is correct
6 Correct 2 ms 9308 KB Output is correct
7 Correct 2 ms 9308 KB Output is correct
8 Correct 2 ms 9308 KB Output is correct
9 Correct 2 ms 9308 KB Output is correct
10 Correct 2 ms 9336 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15188 KB Output is correct
2 Correct 57 ms 13056 KB Output is correct
3 Correct 177 ms 57940 KB Output is correct
4 Correct 60 ms 18004 KB Output is correct
5 Correct 55 ms 18260 KB Output is correct
6 Incorrect 121 ms 46012 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9560 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 2 ms 9560 KB Output is correct
5 Correct 2 ms 9392 KB Output is correct
6 Correct 2 ms 9308 KB Output is correct
7 Correct 2 ms 9308 KB Output is correct
8 Correct 2 ms 9308 KB Output is correct
9 Correct 2 ms 9308 KB Output is correct
10 Correct 2 ms 9336 KB Output is correct
11 Correct 49 ms 15188 KB Output is correct
12 Correct 57 ms 13056 KB Output is correct
13 Correct 177 ms 57940 KB Output is correct
14 Correct 60 ms 18004 KB Output is correct
15 Correct 55 ms 18260 KB Output is correct
16 Incorrect 121 ms 46012 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Incorrect 34 ms 10576 KB Output isn't correct
3 Halted 0 ms 0 KB -