oj.uz

Submission #680572

# Submission time Handle Problem Language Result Execution time Memory
680572 2023-01-11T09:26:31 Z vicious Paths (BOI18_paths) C++17
100 / 100
 326 ms 56680 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define si second
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int N = 300010;
int n,m,k;
int c[N];
vector<int> g[N];
ll dp[40][N], ans;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin.exceptions(ios::badbit|ios::failbit);
    cin>>n>>m>>k;
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        --c[i];
    }
    for (int i = 1; i <= m; ++i) {
        int u,v; cin >>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) dp[(1<<c[i])][i]=1;
    for (int i = 1; i < (1<<k); ++i) {
        for (int j = 1; j <= n; ++j) {
            if (!(i&(1<<c[j]))) continue;
            int p = i^(1<<c[j]);
            for (auto v: g[j]) {
                dp[i][j] += dp[p][v];
            }
        }
    }
    for (int i = 1; i < (1<<k); ++i) {
        if (__builtin_popcount(i)==1) continue;
        for (int j = 1; j <= n; ++j) ans += dp[i][j];
    }
    cout << ans;
    return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 7 ms 7508 KB Output is correct
3 Correct 6 ms 7400 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 6 ms 7380 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7504 KB Output is correct
8 Correct 4 ms 7508 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 14060 KB Output is correct
2 Correct 74 ms 13272 KB Output is correct
3 Correct 241 ms 37828 KB Output is correct
4 Correct 127 ms 15948 KB Output is correct
5 Correct 111 ms 15464 KB Output is correct
6 Correct 184 ms 30232 KB Output is correct
7 Correct 258 ms 37740 KB Output is correct
8 Correct 283 ms 38380 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 7 ms 7508 KB Output is correct
3 Correct 6 ms 7400 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 6 ms 7380 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7504 KB Output is correct
8 Correct 4 ms 7508 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7376 KB Output is correct
11 Correct 71 ms 14060 KB Output is correct
12 Correct 74 ms 13272 KB Output is correct
13 Correct 241 ms 37828 KB Output is correct
14 Correct 127 ms 15948 KB Output is correct
15 Correct 111 ms 15464 KB Output is correct
16 Correct 184 ms 30232 KB Output is correct
17 Correct 258 ms 37740 KB Output is correct
18 Correct 283 ms 38380 KB Output is correct
19 Correct 75 ms 14076 KB Output is correct
20 Correct 65 ms 13244 KB Output is correct
21 Correct 253 ms 37800 KB Output is correct
22 Correct 95 ms 15908 KB Output is correct
23 Correct 90 ms 15452 KB Output is correct
24 Correct 157 ms 30264 KB Output is correct
25 Correct 223 ms 37820 KB Output is correct
26 Correct 253 ms 38440 KB Output is correct
27 Correct 58 ms 13400 KB Output is correct
28 Correct 80 ms 15632 KB Output is correct
29 Correct 295 ms 56544 KB Output is correct
30 Correct 174 ms 35532 KB Output is correct
31 Correct 225 ms 34336 KB Output is correct
32 Correct 326 ms 56680 KB Output is correct
33 Correct 4 ms 7512 KB Output is correct
34 Correct 4 ms 7508 KB Output is correct
35 Correct 5 ms 7380 KB Output is correct
36 Correct 4 ms 7380 KB Output is correct
37 Correct 5 ms 7376 KB Output is correct
38 Correct 6 ms 7504 KB Output is correct
39 Correct 5 ms 7508 KB Output is correct
40 Correct 4 ms 7428 KB Output is correct
41 Correct 5 ms 7388 KB Output is correct
42 Correct 5 ms 7544 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7484 KB Output is correct
2 Correct 21 ms 9592 KB Output is correct
3 Correct 19 ms 9216 KB Output is correct
4 Correct 53 ms 17344 KB Output is correct
5 Correct 51 ms 18132 KB Output is correct
6 Correct 107 ms 36304 KB Output is correct
7 Correct 25 ms 9336 KB Output is correct
8 Correct 74 ms 23640 KB Output is correct
9 Correct 64 ms 24504 KB Output is correct
10 Correct 69 ms 23556 KB Output is correct
11 Correct 92 ms 22768 KB Output is correct
12 Correct 67 ms 28320 KB Output is correct
13 Correct 60 ms 21696 KB Output is correct
14 Correct 142 ms 36336 KB Output is correct
15 Correct 145 ms 36456 KB Output is correct
16 Correct 5 ms 7504 KB Output is correct
17 Correct 5 ms 7520 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 5 ms 7380 KB Output is correct
20 Correct 5 ms 7380 KB Output is correct
21 Correct 5 ms 7508 KB Output is correct
22 Correct 4 ms 7504 KB Output is correct
23 Correct 4 ms 7508 KB Output is correct
24 Correct 4 ms 7380 KB Output is correct
25 Correct 5 ms 7376 KB Output is correct