oj.uz

Submission #952631

# Submission time Handle Problem Language Result Execution time Memory
952631 2024-03-24T11:49:13 Z Ellinor Paths (BOI18_paths) C++14
100 / 100
 439 ms 100436 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize("unroll-loops")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation
#pragma GCC target("movbe")                 // byte swap
#pragma GCC target("aes,pclmul,rdrnd")      // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define rep(i, a, b) for (int i = (a); i < int(b); i++)     // in , ex
#define rrep(i, a, b) for (int i = (a)-1; i >= int(b); i--) // ex, in
#define pb push_back
#define all(x) x.begin(), x.end()

inline void fast()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll INF = 100000000000000000; // 1e17
const ll MOD = 1e9 + 7;

//

random_device rd;
mt19937 rng(rd());
template <typename T>
inline T randint(T lo, T hi) { return uniform_int_distribution<T>(lo, hi)(rng); }

#define int ll
#define float double

//

int N, M, K;
vector<int> nk;
vector<vector<int>> graph;

vector<array<array<array<array<array<ll, 2>, 2>, 2>, 2>, 2>> dp;

ll rec(int nat, int k1, int k2, int k3, int k4, int k5)
{
    if (dp[nat][k1][k2][k3][k4][k5] != -1)
        return dp[nat][k1][k2][k3][k4][k5];
    ll ret = 1;

    for (int u : graph[nat])
    {
        if (nk[u] == 1 && k1 == 0)
            ret += rec(u, 1, k2, k3, k4, k5);
        else if (nk[u] == 2 && k2 == 0)
            ret += rec(u, k1, 1, k3, k4, k5);
        else if (nk[u] == 3 && k3 == 0)
            ret += rec(u, k1, k2, 1, k4, k5);
        else if (nk[u] == 4 && k4 == 0)
            ret += rec(u, k1, k2, k3, 1, k5);
        else if (nk[u] == 5 && k5 == 0)
            ret += rec(u, k1, k2, k3, k4, 1);
    }

    return dp[nat][k1][k2][k3][k4][k5] = ret;
}

int32_t main()
{
    fast();

    cin >> N >> M >> K;

    nk.assign(N, -1);
    rep(i, 0, N) cin >> nk[i];

    graph.assign(N, {});
    int a, b;
    rep(i, 0, M)
    {
        cin >> a >> b;
        a--;
        b--;
        graph[a].pb(b);
        graph[b].pb(a);
    }

    ll ans = 0;

    dp.resize(N);
    // Set all values to -1
    for (auto &arr1 : dp)
    {
        for (auto &arr2 : arr1)
        {
            for (auto &arr3 : arr2)
            {
                for (auto &arr4 : arr3)
                {
                    for (auto &arr5 : arr4)
                    {
                        for (auto &value : arr5)
                        {
                            value = -1;
                        }
                    }
                }
            }
        }
    }

    rep(i, 0, N)
    {
        if (nk[i] == 1)
            ans += rec(i, 1, 0, 0, 0, 0);
        else if (nk[i] == 2)
            ans += rec(i, 0, 1, 0, 0, 0);
        else if (nk[i] == 3)
            ans += rec(i, 0, 0, 1, 0, 0);
        else if (nk[i] == 4)
            ans += rec(i, 0, 0, 0, 1, 0);
        else
            ans += rec(i, 0, 0, 0, 0, 1);
    }

    ans -= N;

    cout << ans << "\n";

    return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 11780 KB Output is correct
2 Correct 54 ms 9940 KB Output is correct
3 Correct 288 ms 99952 KB Output is correct
4 Correct 90 ms 20528 KB Output is correct
5 Correct 77 ms 20308 KB Output is correct
6 Correct 192 ms 69944 KB Output is correct
7 Correct 302 ms 100176 KB Output is correct
8 Correct 297 ms 100432 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 68 ms 11780 KB Output is correct
12 Correct 54 ms 9940 KB Output is correct
13 Correct 288 ms 99952 KB Output is correct
14 Correct 90 ms 20528 KB Output is correct
15 Correct 77 ms 20308 KB Output is correct
16 Correct 192 ms 69944 KB Output is correct
17 Correct 302 ms 100176 KB Output is correct
18 Correct 297 ms 100432 KB Output is correct
19 Correct 65 ms 11868 KB Output is correct
20 Correct 55 ms 10068 KB Output is correct
21 Correct 280 ms 99960 KB Output is correct
22 Correct 82 ms 20416 KB Output is correct
23 Correct 72 ms 20196 KB Output is correct
24 Correct 191 ms 69732 KB Output is correct
25 Correct 304 ms 99892 KB Output is correct
26 Correct 309 ms 100436 KB Output is correct
27 Correct 81 ms 9972 KB Output is correct
28 Correct 134 ms 13996 KB Output is correct
29 Correct 439 ms 100080 KB Output is correct
30 Correct 279 ms 55272 KB Output is correct
31 Correct 310 ms 55468 KB Output is correct
32 Correct 413 ms 100024 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 344 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 48 ms 3420 KB Output is correct
3 Correct 22 ms 3420 KB Output is correct
4 Correct 64 ms 33360 KB Output is correct
5 Correct 47 ms 33736 KB Output is correct
6 Correct 127 ms 33516 KB Output is correct
7 Correct 28 ms 3492 KB Output is correct
8 Correct 89 ms 33500 KB Output is correct
9 Correct 54 ms 33736 KB Output is correct
10 Correct 74 ms 33564 KB Output is correct
11 Correct 88 ms 18320 KB Output is correct
12 Correct 66 ms 26044 KB Output is correct
13 Correct 66 ms 18372 KB Output is correct
14 Correct 111 ms 33512 KB Output is correct
15 Correct 86 ms 33368 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct