oj.uz

Submission #873319

# Submission time Handle Problem Language Result Execution time Memory
873319 2023-11-14T20:06:34 Z bobbilyking Paths (BOI18_paths) C++17
100 / 100
 292 ms 100476 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)
 
#define NN 300010
#define M 1000000007 // 998244353

ll dp[NN][1<<5];
vector<ll> adj[NN];
ll col[NN];

ll rec(ll i, ll bm) {
    auto &DP = dp[i][bm];
    if (!~DP) {
        DP = 1;
        for (auto x: adj[i]) if (!((1<<col[x])&bm)) {
            DP += rec(x, bm|(1<<col[x]));
        }
    }
    return DP;
}

int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    G(n) G(m) G(k)
    F(i, 1, n+1) {
        cin >> col[i]; --col[i];
    }    
    while(m--){
        G(x) G(y) adj[x].push_back(y); adj[y].push_back(x);
    }
    memset(dp, -1, sizeof dp);
    ll ans = 0;
    F(i, 1, n+1) {
        // cout << i << ": " << rec(i, 1<<col[i]) << endl;
        ans += rec(i, 1<<col[i]);
    }
    cout << ans-n << '\n';
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 82520 KB Output is correct
2 Correct 12 ms 82520 KB Output is correct
3 Correct 11 ms 82708 KB Output is correct
4 Correct 11 ms 82780 KB Output is correct
5 Correct 11 ms 82524 KB Output is correct
6 Correct 11 ms 82768 KB Output is correct
7 Correct 11 ms 82780 KB Output is correct
8 Correct 11 ms 82780 KB Output is correct
9 Correct 11 ms 82524 KB Output is correct
10 Correct 11 ms 82780 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 92708 KB Output is correct
2 Correct 54 ms 91984 KB Output is correct
3 Correct 238 ms 99984 KB Output is correct
4 Correct 83 ms 96336 KB Output is correct
5 Correct 70 ms 96312 KB Output is correct
6 Correct 144 ms 97932 KB Output is correct
7 Correct 233 ms 99988 KB Output is correct
8 Correct 209 ms 100476 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 82520 KB Output is correct
2 Correct 12 ms 82520 KB Output is correct
3 Correct 11 ms 82708 KB Output is correct
4 Correct 11 ms 82780 KB Output is correct
5 Correct 11 ms 82524 KB Output is correct
6 Correct 11 ms 82768 KB Output is correct
7 Correct 11 ms 82780 KB Output is correct
8 Correct 11 ms 82780 KB Output is correct
9 Correct 11 ms 82524 KB Output is correct
10 Correct 11 ms 82780 KB Output is correct
11 Correct 64 ms 92708 KB Output is correct
12 Correct 54 ms 91984 KB Output is correct
13 Correct 238 ms 99984 KB Output is correct
14 Correct 83 ms 96336 KB Output is correct
15 Correct 70 ms 96312 KB Output is correct
16 Correct 144 ms 97932 KB Output is correct
17 Correct 233 ms 99988 KB Output is correct
18 Correct 209 ms 100476 KB Output is correct
19 Correct 65 ms 92756 KB Output is correct
20 Correct 53 ms 92116 KB Output is correct
21 Correct 227 ms 100052 KB Output is correct
22 Correct 84 ms 96340 KB Output is correct
23 Correct 71 ms 96340 KB Output is correct
24 Correct 142 ms 97904 KB Output is correct
25 Correct 217 ms 99980 KB Output is correct
26 Correct 192 ms 100296 KB Output is correct
27 Correct 67 ms 91988 KB Output is correct
28 Correct 84 ms 94032 KB Output is correct
29 Correct 292 ms 100196 KB Output is correct
30 Correct 195 ms 97696 KB Output is correct
31 Correct 241 ms 97696 KB Output is correct
32 Correct 249 ms 99920 KB Output is correct
33 Correct 12 ms 82524 KB Output is correct
34 Correct 11 ms 82628 KB Output is correct
35 Correct 11 ms 82780 KB Output is correct
36 Correct 11 ms 82520 KB Output is correct
37 Correct 11 ms 82932 KB Output is correct
38 Correct 10 ms 82524 KB Output is correct
39 Correct 11 ms 82524 KB Output is correct
40 Correct 11 ms 82660 KB Output is correct
41 Correct 10 ms 82524 KB Output is correct
42 Correct 10 ms 82524 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 82524 KB Output is correct
2 Correct 38 ms 85596 KB Output is correct
3 Correct 25 ms 85592 KB Output is correct
4 Correct 53 ms 89836 KB Output is correct
5 Correct 46 ms 90060 KB Output is correct
6 Correct 72 ms 89848 KB Output is correct
7 Correct 30 ms 85608 KB Output is correct
8 Correct 61 ms 89772 KB Output is correct
9 Correct 55 ms 90052 KB Output is correct
10 Correct 56 ms 89956 KB Output is correct
11 Correct 71 ms 88688 KB Output is correct
12 Correct 53 ms 89200 KB Output is correct
13 Correct 57 ms 88904 KB Output is correct
14 Correct 70 ms 89680 KB Output is correct
15 Correct 67 ms 89948 KB Output is correct
16 Correct 12 ms 82744 KB Output is correct
17 Correct 10 ms 82524 KB Output is correct
18 Correct 11 ms 82660 KB Output is correct
19 Correct 11 ms 82780 KB Output is correct
20 Correct 11 ms 82776 KB Output is correct
21 Correct 11 ms 82524 KB Output is correct
22 Correct 11 ms 82524 KB Output is correct
23 Correct 10 ms 82524 KB Output is correct
24 Correct 11 ms 82524 KB Output is correct
25 Correct 10 ms 82764 KB Output is correct