oj.uz

Submission #263609

# Submission time Handle Problem Language Result Execution time Memory
263609 2020-08-13T21:06:42 Z Hehehe Paths (BOI18_paths) C++14
100 / 100
 525 ms 107512 KB 
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<long double, long double>
#define sz(x) (int)((x).size())
#define int long long

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 3e5 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

int n, m, k, dp[N][35], c[N];
vector<int>v[N];


void solve(){

    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++){
        cin >> c[i];
        c[i]--;
    }

    for(int i = 1; i <= n; i++){
        dp[i][(1 << c[i])] = 1;
    }

    for(int i = 1, x, y; i <= m; i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(int mask = 1; mask < (1 << k); mask++){
        for(int i = 1; i <= n; i++){
            if(!dp[i][mask])continue;
            for(auto it : v[i]){
                if(mask & (1 << c[it]))continue;
                dp[it][mask | (1 << c[it])] += dp[i][mask];
            }
        }
    }

    int ans = 0;
    for(int mask = 1; mask < (1 << k); mask++){
        for(int i = 1; i <= n; i++){
            ans += dp[i][mask];
        }
    }

    cout << ans - n << '\n';
}



int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //cout << setprecision(6) << fixed;

    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}

Subtask #1
23.0 / 23.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 15864 KB Output is correct
2 Correct 92 ms 14588 KB Output is correct
3 Correct 453 ms 102484 KB Output is correct
4 Correct 152 ms 24056 KB Output is correct
5 Correct 136 ms 23984 KB Output is correct
6 Correct 321 ms 72628 KB Output is correct
7 Correct 430 ms 107028 KB Output is correct
8 Correct 424 ms 107512 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 6 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 5 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 6 ms 7424 KB Output is correct
9 Correct 5 ms 7424 KB Output is correct
10 Correct 5 ms 7424 KB Output is correct
11 Correct 117 ms 15864 KB Output is correct
12 Correct 92 ms 14588 KB Output is correct
13 Correct 453 ms 102484 KB Output is correct
14 Correct 152 ms 24056 KB Output is correct
15 Correct 136 ms 23984 KB Output is correct
16 Correct 321 ms 72628 KB Output is correct
17 Correct 430 ms 107028 KB Output is correct
18 Correct 424 ms 107512 KB Output is correct
19 Correct 102 ms 18680 KB Output is correct
20 Correct 76 ms 17008 KB Output is correct
21 Correct 421 ms 107060 KB Output is correct
22 Correct 149 ms 27256 KB Output is correct
23 Correct 125 ms 27256 KB Output is correct
24 Correct 281 ms 76772 KB Output is correct
25 Correct 410 ms 107000 KB Output is correct
26 Correct 419 ms 107512 KB Output is correct
27 Correct 99 ms 17016 KB Output is correct
28 Correct 147 ms 21112 KB Output is correct
29 Correct 525 ms 107004 KB Output is correct
30 Correct 362 ms 62412 KB Output is correct
31 Correct 355 ms 62444 KB Output is correct
32 Correct 520 ms 107008 KB Output is correct
33 Correct 5 ms 7424 KB Output is correct
34 Correct 6 ms 7424 KB Output is correct
35 Correct 6 ms 7424 KB Output is correct
36 Correct 5 ms 7424 KB Output is correct
37 Correct 6 ms 7424 KB Output is correct
38 Correct 5 ms 7424 KB Output is correct
39 Correct 5 ms 7424 KB Output is correct
40 Correct 6 ms 7424 KB Output is correct
41 Correct 5 ms 7424 KB Output is correct
42 Correct 6 ms 7424 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 52 ms 9600 KB Output is correct
3 Correct 30 ms 10368 KB Output is correct
4 Correct 133 ms 40440 KB Output is correct
5 Correct 96 ms 40812 KB Output is correct
6 Correct 199 ms 40440 KB Output is correct
7 Correct 39 ms 10368 KB Output is correct
8 Correct 143 ms 40508 KB Output is correct
9 Correct 102 ms 40812 KB Output is correct
10 Correct 156 ms 41100 KB Output is correct
11 Correct 126 ms 25328 KB Output is correct
12 Correct 107 ms 33000 KB Output is correct
13 Correct 112 ms 25584 KB Output is correct
14 Correct 176 ms 40472 KB Output is correct
15 Correct 175 ms 40484 KB Output is correct
16 Correct 5 ms 7424 KB Output is correct
17 Correct 5 ms 7424 KB Output is correct
18 Correct 6 ms 7424 KB Output is correct
19 Correct 5 ms 7424 KB Output is correct
20 Correct 6 ms 7424 KB Output is correct
21 Correct 5 ms 7424 KB Output is correct
22 Correct 6 ms 7424 KB Output is correct
23 Correct 5 ms 7400 KB Output is correct
24 Correct 5 ms 7424 KB Output is correct
25 Correct 5 ms 7424 KB Output is correct