oj.uz

Submission #76070

# Submission time Handle Problem Language Result Execution time Memory
76070 2018-09-12T03:20:36 Z luciocf Paths (BOI18_paths) C++14
100 / 100
 1683 ms 1009524 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5+10;
const int MAXK = 6;

typedef long long ll;

int n, m, k, num[MAXN];
ll dp[MAXN][MAXK][1<<MAXK];
vector<int> grafo[MAXN];

ll solve(int u, int qtd, int mask)
{
    if (qtd == 1) return 1;
    if (dp[u][qtd][mask] != -1) return dp[u][qtd][mask];

    ll ans = 0LL;
    for (int i = 0; i < (int) grafo[u].size(); i++)
    {
        int v = grafo[u][i];
        int c = num[v];

        if (!(mask&(1<<c))) ans += solve(v, qtd-1, mask|(1<<c));
    }
    return dp[u][qtd][mask] = ans;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> k;

    for (int i = 0; i < n; i++) cin >> num[i];

    while (m--)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        grafo[a].push_back(b); grafo[b].push_back(a);
    }

    ll ans = 0LL;
    for (int l = 2; l <= k; l++)
    {
        memset(dp, -1, sizeof dp);
        for (int i = 0; i < n; i++) ans += solve(i, l, (1<<num[i]));
    }
    cout << ans << "\n";
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1043 ms 909432 KB Output is correct
2 Correct 1042 ms 909588 KB Output is correct
3 Correct 878 ms 909672 KB Output is correct
4 Correct 698 ms 909672 KB Output is correct
5 Correct 8 ms 909672 KB Output is correct
6 Correct 1071 ms 909672 KB Output is correct
7 Correct 1051 ms 909672 KB Output is correct
8 Correct 1052 ms 909768 KB Output is correct
9 Correct 1033 ms 909816 KB Output is correct
10 Correct 881 ms 909816 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1174 ms 916116 KB Output is correct
2 Correct 980 ms 918360 KB Output is correct
3 Correct 1270 ms 928908 KB Output is correct
4 Correct 825 ms 928908 KB Output is correct
5 Correct 138 ms 928908 KB Output is correct
6 Correct 1228 ms 938056 KB Output is correct
7 Correct 1290 ms 944212 KB Output is correct
8 Correct 1265 ms 949600 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1043 ms 909432 KB Output is correct
2 Correct 1042 ms 909588 KB Output is correct
3 Correct 878 ms 909672 KB Output is correct
4 Correct 698 ms 909672 KB Output is correct
5 Correct 8 ms 909672 KB Output is correct
6 Correct 1071 ms 909672 KB Output is correct
7 Correct 1051 ms 909672 KB Output is correct
8 Correct 1052 ms 909768 KB Output is correct
9 Correct 1033 ms 909816 KB Output is correct
10 Correct 881 ms 909816 KB Output is correct
11 Correct 1174 ms 916116 KB Output is correct
12 Correct 980 ms 918360 KB Output is correct
13 Correct 1270 ms 928908 KB Output is correct
14 Correct 825 ms 928908 KB Output is correct
15 Correct 138 ms 928908 KB Output is correct
16 Correct 1228 ms 938056 KB Output is correct
17 Correct 1290 ms 944212 KB Output is correct
18 Correct 1265 ms 949600 KB Output is correct
19 Correct 1000 ms 949600 KB Output is correct
20 Correct 991 ms 949600 KB Output is correct
21 Correct 1324 ms 958288 KB Output is correct
22 Correct 979 ms 958288 KB Output is correct
23 Correct 144 ms 958288 KB Output is correct
24 Correct 1193 ms 967224 KB Output is correct
25 Correct 1330 ms 973492 KB Output is correct
26 Correct 1309 ms 978092 KB Output is correct
27 Correct 1171 ms 978092 KB Output is correct
28 Correct 1214 ms 978092 KB Output is correct
29 Correct 1627 ms 986944 KB Output is correct
30 Correct 1488 ms 987920 KB Output is correct
31 Correct 1495 ms 992144 KB Output is correct
32 Correct 1683 ms 999788 KB Output is correct
33 Correct 1048 ms 999788 KB Output is correct
34 Correct 1044 ms 999788 KB Output is correct
35 Correct 887 ms 999788 KB Output is correct
36 Correct 707 ms 999788 KB Output is correct
37 Correct 9 ms 999788 KB Output is correct
38 Correct 1060 ms 999788 KB Output is correct
39 Correct 1053 ms 999788 KB Output is correct
40 Correct 1051 ms 999788 KB Output is correct
41 Correct 1046 ms 999788 KB Output is correct
42 Correct 887 ms 999788 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1234 ms 999788 KB Output is correct
2 Correct 1305 ms 999788 KB Output is correct
3 Correct 950 ms 999788 KB Output is correct
4 Correct 963 ms 999788 KB Output is correct
5 Correct 968 ms 999788 KB Output is correct
6 Correct 1431 ms 999788 KB Output is correct
7 Correct 1084 ms 999788 KB Output is correct
8 Correct 1187 ms 1000452 KB Output is correct
9 Correct 1190 ms 1002388 KB Output is correct
10 Correct 1195 ms 1003676 KB Output is correct
11 Correct 1394 ms 1003676 KB Output is correct
12 Correct 1354 ms 1005288 KB Output is correct
13 Correct 1395 ms 1005740 KB Output is correct
14 Correct 1427 ms 1008076 KB Output is correct
15 Correct 1404 ms 1009524 KB Output is correct
16 Correct 1058 ms 1009524 KB Output is correct
17 Correct 1044 ms 1009524 KB Output is correct
18 Correct 894 ms 1009524 KB Output is correct
19 Correct 701 ms 1009524 KB Output is correct
20 Correct 8 ms 1009524 KB Output is correct
21 Correct 1043 ms 1009524 KB Output is correct
22 Correct 1028 ms 1009524 KB Output is correct
23 Correct 1038 ms 1009524 KB Output is correct
24 Correct 1039 ms 1009524 KB Output is correct
25 Correct 872 ms 1009524 KB Output is correct