oj.uz

Submission #1110333

# Submission time Handle Problem Language Result Execution time Memory
1110333 2024-11-09T09:17:45 Z ljtunas Paths (BOI18_paths) C++17
53 / 100
 137 ms 61380 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 = 1e5 + 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 2 ms 3152 KB Output is correct
2 Correct 1 ms 3152 KB Output is correct
3 Correct 2 ms 3152 KB Output is correct
4 Correct 2 ms 3152 KB Output is correct
5 Correct 1 ms 3152 KB Output is correct
6 Correct 2 ms 3152 KB Output is correct
7 Correct 2 ms 3152 KB Output is correct
8 Correct 2 ms 3152 KB Output is correct
9 Correct 2 ms 3152 KB Output is correct
10 Correct 2 ms 3152 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 14664 KB Output is correct
2 Correct 49 ms 12404 KB Output is correct
3 Incorrect 5 ms 3920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 1 ms 3152 KB Output is correct
3 Correct 2 ms 3152 KB Output is correct
4 Correct 2 ms 3152 KB Output is correct
5 Correct 1 ms 3152 KB Output is correct
6 Correct 2 ms 3152 KB Output is correct
7 Correct 2 ms 3152 KB Output is correct
8 Correct 2 ms 3152 KB Output is correct
9 Correct 2 ms 3152 KB Output is correct
10 Correct 2 ms 3152 KB Output is correct
11 Correct 63 ms 14664 KB Output is correct
12 Correct 49 ms 12404 KB Output is correct
13 Incorrect 5 ms 3920 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3152 KB Output is correct
2 Correct 42 ms 7728 KB Output is correct
3 Correct 19 ms 7504 KB Output is correct
4 Correct 61 ms 61004 KB Output is correct
5 Correct 39 ms 61380 KB Output is correct
6 Correct 119 ms 61008 KB Output is correct
7 Correct 32 ms 7452 KB Output is correct
8 Correct 81 ms 61008 KB Output is correct
9 Correct 72 ms 61380 KB Output is correct
10 Correct 67 ms 61124 KB Output is correct
11 Correct 75 ms 35184 KB Output is correct
12 Correct 71 ms 48192 KB Output is correct
13 Correct 86 ms 35128 KB Output is correct
14 Correct 137 ms 61116 KB Output is correct
15 Correct 117 ms 61012 KB Output is correct
16 Correct 2 ms 3152 KB Output is correct
17 Correct 1 ms 3152 KB Output is correct
18 Correct 2 ms 3152 KB Output is correct
19 Correct 1 ms 3152 KB Output is correct
20 Correct 1 ms 3152 KB Output is correct
21 Correct 2 ms 3152 KB Output is correct
22 Correct 2 ms 3152 KB Output is correct
23 Correct 1 ms 3152 KB Output is correct
24 Correct 2 ms 3152 KB Output is correct
25 Correct 2 ms 3152 KB Output is correct