oj.uz

Submission #1110334

# Submission time Handle Problem Language Result Execution time Memory
1110334 2024-11-09T09:18:19 Z ljtunas Paths (BOI18_paths) C++17
100 / 100
 344 ms 194376 KB 
// author : anhtun_hi , nqg
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define reset(h, v)    memset(h, v, sizeof h)
#define Forv(i, a)     for(auto& i : a)
#define For(i, a, b)   for(int i = a; i <= b; ++i)
#define Ford(i, a, b)  for(int i = a; i >= b; --i)
#define c_bit(i)     __builtin_popcountll(i)
#define Bit(mask, i)    ((mask >> i) & 1LL)
#define onbit(mask, i)  ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))
using namespace std;
namespace std {
    template <typename T, int D>
    struct _vector : public vector <_vector <T, D - 1>> {
        static_assert(D >= 1, "Dimension must be positive!");
        template <typename... Args>
        _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
    };
    template <typename T> struct _vector <T, 1> : public vector <T> {
        _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
    };
    template <class A, class B> bool minimize(A &a, B b){return a > b ? a = b, true : false;}
    template <class A, class B> bool maximize(A &a, B b){return a < b ? a = b, true : false;}
}
const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0}, LOG = 20, base = 311, inf = 1e9 + 5;
const int MAXN = 5e5 + 5;
const  ll  mod = 1e9 + 7;
const  ll   oo = 1e18;

#define int long long

int n, m, k, c[MAXN]; vector<int> g[MAXN];
ll dp[MAXN][(1 << 6) + 5];

void Solve() {
    cin >> n >> m >> k;
    For(i, 1, n) cin >> c[i], --c[i];
    For(i, 1, m){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    For(i, 1, n) dp[i][1 << c[i]] ++;
    ll ans = 0;
    For(s, 1, (1 << k) - 1) {
        For(i, 1, n){
            Forv(j, g[i]) {
                if(Bit(s, c[j]) == 0){
                    ans -= dp[j][onbit(s, c[j])];
                    dp[j][onbit(s, c[j])] += dp[i][s];
                    ans += dp[j][onbit(s, c[j])];
                }
            }
        }
    }
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(0);
    if(fopen("BOI18_paths.inp", "r")) {
        freopen("BOI18_paths.inp", "r", stdin);
        freopen("BOI18_paths.out", "w", stdout);
    }

    int t = 1;
//    cin >> t;

    for (int test = 1; test <= t; test++) {
        Solve();
    }
    return 0;
}

Compilation message

paths.cpp: In function 'int32_t main()':
paths.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen("BOI18_paths.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen("BOI18_paths.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 26352 KB Output is correct
2 Correct 54 ms 23880 KB Output is correct
3 Correct 241 ms 193352 KB Output is correct
4 Correct 87 ms 42828 KB Output is correct
5 Correct 64 ms 42740 KB Output is correct
6 Correct 147 ms 139040 KB Output is correct
7 Correct 211 ms 193884 KB Output is correct
8 Correct 205 ms 194376 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Correct 3 ms 14672 KB Output is correct
3 Correct 3 ms 14672 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 3 ms 14672 KB Output is correct
10 Correct 3 ms 14672 KB Output is correct
11 Correct 68 ms 26352 KB Output is correct
12 Correct 54 ms 23880 KB Output is correct
13 Correct 241 ms 193352 KB Output is correct
14 Correct 87 ms 42828 KB Output is correct
15 Correct 64 ms 42740 KB Output is correct
16 Correct 147 ms 139040 KB Output is correct
17 Correct 211 ms 193884 KB Output is correct
18 Correct 205 ms 194376 KB Output is correct
19 Correct 76 ms 29092 KB Output is correct
20 Correct 55 ms 26184 KB Output is correct
21 Correct 214 ms 193864 KB Output is correct
22 Correct 88 ms 42808 KB Output is correct
23 Correct 66 ms 42908 KB Output is correct
24 Correct 149 ms 139192 KB Output is correct
25 Correct 256 ms 193788 KB Output is correct
26 Correct 212 ms 194376 KB Output is correct
27 Correct 79 ms 26340 KB Output is correct
28 Correct 99 ms 32588 KB Output is correct
29 Correct 331 ms 193924 KB Output is correct
30 Correct 197 ms 110708 KB Output is correct
31 Correct 221 ms 109756 KB Output is correct
32 Correct 344 ms 193864 KB Output is correct
33 Correct 3 ms 14672 KB Output is correct
34 Correct 3 ms 14780 KB Output is correct
35 Correct 3 ms 14844 KB Output is correct
36 Correct 3 ms 14672 KB Output is correct
37 Correct 3 ms 14672 KB Output is correct
38 Correct 3 ms 14808 KB Output is correct
39 Correct 4 ms 14928 KB Output is correct
40 Correct 3 ms 14672 KB Output is correct
41 Correct 3 ms 14672 KB Output is correct
42 Correct 3 ms 14844 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Correct 52 ms 19536 KB Output is correct
3 Correct 19 ms 19028 KB Output is correct
4 Correct 57 ms 73800 KB Output is correct
5 Correct 40 ms 74172 KB Output is correct
6 Correct 121 ms 73824 KB Output is correct
7 Correct 28 ms 19024 KB Output is correct
8 Correct 76 ms 73916 KB Output is correct
9 Correct 63 ms 74180 KB Output is correct
10 Correct 59 ms 73916 KB Output is correct
11 Correct 77 ms 46292 KB Output is correct
12 Correct 94 ms 59096 KB Output is correct
13 Correct 86 ms 47160 KB Output is correct
14 Correct 117 ms 73868 KB Output is correct
15 Correct 126 ms 73804 KB Output is correct
16 Correct 3 ms 14840 KB Output is correct
17 Correct 3 ms 14672 KB Output is correct
18 Correct 3 ms 14780 KB Output is correct
19 Correct 3 ms 14672 KB Output is correct
20 Correct 2 ms 14672 KB Output is correct
21 Correct 3 ms 14672 KB Output is correct
22 Correct 3 ms 14672 KB Output is correct
23 Correct 3 ms 14780 KB Output is correct
24 Correct 2 ms 14784 KB Output is correct
25 Correct 3 ms 14672 KB Output is correct