oj.uz

Submission #984459

# Submission time Handle Problem Language Result Execution time Memory
984459 2024-05-16T17:04:26 Z Mizo_Compiler Paths (BOI18_paths) C++17
100 / 100
 264 ms 80300 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("popcnt")
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
const int N = 3e5, N2 = 1e5;
int n, m, k, col[N];
ll dp[N][(1 << 4)], dp2[N2][(1 << 5)], ans = 0;
vector<int> adj[N];

ll sol(int u, int msk) {
    ll &ret = dp[u][msk];
    if (~ret)return ret;
    ret = 1;
    msk |= (1 << col[u]);
    for (auto &v : adj[u]) {
        if ((msk & (1 << col[v])))continue;
        ret = ret + sol(v, msk);
    }
    return ret;
}

ll sol2(int u, int msk) {
    ll &ret = dp2[u][msk];
    if (~ret)return ret;
    ret = 1;
    msk |= (1 << col[u]);
    for (auto &v : adj[u]) {
        if ((msk & (1 << col[v])))continue;
        ret = ret + sol2(v, msk);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> col[i];
        --col[i];
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    memset(dp, -1, sizeof dp);
    memset(dp2, -1, sizeof dp2);
    if (n > int(1e5)) {
        for (int i = 0; i < n; i++) {
            ans = ans + sol(i, 0);
        }
    } else {
        for (int i = 0; i < n; i++) {
            ans = ans + sol2(i, 0);
        }
    }
    cout << ans - ll(n);
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 70236 KB Output is correct
2 Correct 10 ms 70236 KB Output is correct
3 Correct 10 ms 70236 KB Output is correct
4 Correct 11 ms 70324 KB Output is correct
5 Correct 11 ms 70236 KB Output is correct
6 Correct 11 ms 70328 KB Output is correct
7 Correct 10 ms 70320 KB Output is correct
8 Correct 11 ms 70236 KB Output is correct
9 Correct 11 ms 70236 KB Output is correct
10 Correct 11 ms 70236 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 73820 KB Output is correct
2 Correct 49 ms 73820 KB Output is correct
3 Correct 197 ms 79444 KB Output is correct
4 Correct 76 ms 74772 KB Output is correct
5 Correct 74 ms 74796 KB Output is correct
6 Correct 142 ms 77876 KB Output is correct
7 Correct 200 ms 79460 KB Output is correct
8 Correct 191 ms 80300 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 70236 KB Output is correct
2 Correct 10 ms 70236 KB Output is correct
3 Correct 10 ms 70236 KB Output is correct
4 Correct 11 ms 70324 KB Output is correct
5 Correct 11 ms 70236 KB Output is correct
6 Correct 11 ms 70328 KB Output is correct
7 Correct 10 ms 70320 KB Output is correct
8 Correct 11 ms 70236 KB Output is correct
9 Correct 11 ms 70236 KB Output is correct
10 Correct 11 ms 70236 KB Output is correct
11 Correct 58 ms 73820 KB Output is correct
12 Correct 49 ms 73820 KB Output is correct
13 Correct 197 ms 79444 KB Output is correct
14 Correct 76 ms 74772 KB Output is correct
15 Correct 74 ms 74796 KB Output is correct
16 Correct 142 ms 77876 KB Output is correct
17 Correct 200 ms 79460 KB Output is correct
18 Correct 191 ms 80300 KB Output is correct
19 Correct 58 ms 73812 KB Output is correct
20 Correct 49 ms 73816 KB Output is correct
21 Correct 203 ms 79440 KB Output is correct
22 Correct 73 ms 74760 KB Output is correct
23 Correct 67 ms 74580 KB Output is correct
24 Correct 136 ms 77936 KB Output is correct
25 Correct 197 ms 79592 KB Output is correct
26 Correct 213 ms 80228 KB Output is correct
27 Correct 58 ms 73768 KB Output is correct
28 Correct 76 ms 74576 KB Output is correct
29 Correct 255 ms 79700 KB Output is correct
30 Correct 168 ms 76484 KB Output is correct
31 Correct 180 ms 76528 KB Output is correct
32 Correct 264 ms 79696 KB Output is correct
33 Correct 10 ms 70236 KB Output is correct
34 Correct 10 ms 70236 KB Output is correct
35 Correct 10 ms 70232 KB Output is correct
36 Correct 12 ms 70236 KB Output is correct
37 Correct 11 ms 70344 KB Output is correct
38 Correct 10 ms 70232 KB Output is correct
39 Correct 11 ms 70236 KB Output is correct
40 Correct 10 ms 70236 KB Output is correct
41 Correct 10 ms 70236 KB Output is correct
42 Correct 10 ms 70252 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 70236 KB Output is correct
2 Correct 34 ms 71504 KB Output is correct
3 Correct 23 ms 71256 KB Output is correct
4 Correct 63 ms 73284 KB Output is correct
5 Correct 50 ms 73904 KB Output is correct
6 Correct 73 ms 73296 KB Output is correct
7 Correct 27 ms 71260 KB Output is correct
8 Correct 60 ms 73256 KB Output is correct
9 Correct 47 ms 74008 KB Output is correct
10 Correct 57 ms 73648 KB Output is correct
11 Correct 57 ms 72148 KB Output is correct
12 Correct 55 ms 73092 KB Output is correct
13 Correct 56 ms 72272 KB Output is correct
14 Correct 72 ms 73040 KB Output is correct
15 Correct 63 ms 73308 KB Output is correct
16 Correct 10 ms 70232 KB Output is correct
17 Correct 10 ms 70236 KB Output is correct
18 Correct 10 ms 70236 KB Output is correct
19 Correct 10 ms 70400 KB Output is correct
20 Correct 10 ms 70232 KB Output is correct
21 Correct 10 ms 70236 KB Output is correct
22 Correct 10 ms 70316 KB Output is correct
23 Correct 10 ms 70232 KB Output is correct
24 Correct 11 ms 70236 KB Output is correct
25 Correct 11 ms 70236 KB Output is correct