oj.uz

Submission #792702

# Submission time Handle Problem Language Result Execution time Memory
792702 2023-07-25T08:10:41 Z TheSahib Paths (BOI18_paths) C++17
53 / 100
 201 ms 56984 KB 
#include <bits/stdc++.h>

#define ll long long
#define oo 1e9
#define pii pair<int, int>

using namespace std;

const int MAX = 1e5 + 5;

int n, m, k; 
int color[MAX];
vector<int> g[MAX];

ll dp[MAX][1 << 5];

void solve(){
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> color[i];
        color[i]--;
        dp[i][1 << color[i]] = 1;
    }
    for (int i = 0; i < m; i++)
    {
        int u, v; cin >> u >> v;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    ll ans = 0;
    for (int mask = 1; mask < (1 << k); mask++)
    {
        if(__popcount(mask) <= 1) continue;
        for (int node = 1; node <= n; node++)
        {
            if(!(mask & (1 << color[node]))) continue;
            for(int to:g[node]){
                dp[node][mask] += dp[to][mask ^ (1 << color[node])];
            }
            ans += dp[node][mask];
        }
    }
    cout << ans << '\n';
}

int main()
{
    solve();
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2660 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 10308 KB Output is correct
2 Correct 113 ms 8676 KB Output is correct
3 Runtime error 46 ms 56984 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2660 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 125 ms 10308 KB Output is correct
12 Correct 113 ms 8676 KB Output is correct
13 Runtime error 46 ms 56984 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 35 ms 4620 KB Output is correct
3 Correct 32 ms 4564 KB Output is correct
4 Correct 85 ms 32212 KB Output is correct
5 Correct 77 ms 32928 KB Output is correct
6 Correct 201 ms 32208 KB Output is correct
7 Correct 32 ms 4604 KB Output is correct
8 Correct 173 ms 32208 KB Output is correct
9 Correct 119 ms 32980 KB Output is correct
10 Correct 97 ms 32948 KB Output is correct
11 Correct 79 ms 18220 KB Output is correct
12 Correct 99 ms 25716 KB Output is correct
13 Correct 91 ms 18484 KB Output is correct
14 Correct 170 ms 32212 KB Output is correct
15 Correct 157 ms 32300 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 1 ms 2660 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2660 KB Output is correct
20 Correct 1 ms 2660 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 1 ms 2644 KB Output is correct
25 Correct 1 ms 2644 KB Output is correct