oj.uz

Submission #440949

# Submission time Handle Problem Language Result Execution time Memory
440949 2021-07-03T15:32:33 Z BeanZ Paths (BOI18_paths) C++14
53 / 100
 323 ms 62648 KB 
// I_Love_LPL 11m
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e5 + 5;
long long mod = 998244353;
const int lim = 4e5 + 5;
const int lg = 22;
const int base = 311;
const long double eps = 1e-6;
ll dp[N][(2 << 5) + 5], c[N];
vector<ll> node[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= m; i++){
        ll u, v;
        cin >> u >> v;
        node[u].push_back(v);
        node[v].push_back(u);
    }
    for (int i = 1; i <= n; i++){
        dp[i][(1 << (c[i] - 1))] = 1;
    }
    ll ans = 0;
    for (int i = 0; i < (1 << k); i++){
        for (int g = 1; g <= n; g++){
            if (i & (1 << (c[g] - 1))){
                for (auto d : node[g]){
                    dp[g][i] += dp[d][i ^ (1 << (c[g] - 1))];
                }
            }
            ans = ans + dp[g][i];
        }
    }
    cout << ans - n;
}
/*
Ans:

Out:
*/

Compilation message

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

Subtask #1
23.0 / 23.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 15380 KB Output is correct
2 Correct 69 ms 12416 KB Output is correct
3 Runtime error 32 ms 10716 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2632 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2672 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 90 ms 15380 KB Output is correct
12 Correct 69 ms 12416 KB Output is correct
13 Runtime error 32 ms 10716 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 27 ms 5860 KB Output is correct
3 Correct 24 ms 5808 KB Output is correct
4 Correct 131 ms 62244 KB Output is correct
5 Correct 101 ms 62616 KB Output is correct
6 Correct 291 ms 62308 KB Output is correct
7 Correct 32 ms 5836 KB Output is correct
8 Correct 172 ms 62300 KB Output is correct
9 Correct 122 ms 62648 KB Output is correct
10 Correct 165 ms 62356 KB Output is correct
11 Correct 165 ms 33828 KB Output is correct
12 Correct 181 ms 48208 KB Output is correct
13 Correct 145 ms 33960 KB Output is correct
14 Correct 284 ms 62316 KB Output is correct
15 Correct 323 ms 62344 KB Output is correct
16 Correct 2 ms 2676 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 2 ms 2636 KB Output is correct
23 Correct 3 ms 2636 KB Output is correct
24 Correct 2 ms 2636 KB Output is correct
25 Correct 2 ms 2636 KB Output is correct