oj.uz

Submission #263607

# Submission time Handle Problem Language Result Execution time Memory
263607 2020-08-13T21:05:34 Z Hehehe Paths (BOI18_paths) C++14
23 / 100
 371 ms 71928 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][(1 << 5) + 11], 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 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7424 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 6 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 5 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 14712 KB Output is correct
2 Correct 72 ms 13304 KB Output is correct
3 Correct 371 ms 71928 KB Output is correct
4 Correct 117 ms 20344 KB Output is correct
5 Correct 115 ms 20344 KB Output is correct
6 Incorrect 310 ms 53204 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7424 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 6 ms 7424 KB Output is correct
7 Correct 6 ms 7424 KB Output is correct
8 Correct 5 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 85 ms 14712 KB Output is correct
12 Correct 72 ms 13304 KB Output is correct
13 Correct 371 ms 71928 KB Output is correct
14 Correct 117 ms 20344 KB Output is correct
15 Correct 115 ms 20344 KB Output is correct
16 Incorrect 310 ms 53204 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Incorrect 46 ms 9344 KB Output isn't correct
3 Halted 0 ms 0 KB -