oj.uz

Submission #59154

# Submission time Handle Problem Language Result Execution time Memory
59154 2018-07-20T19:53:06 Z Benq Paths (BOI18_paths) C++14
53 / 100
 473 ms 53904 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int N,M,K, col[MX];
vi adj[MX];
ll dp[MX][32];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> K;
    FOR(i,1,N+1) {
        cin >> col[i];
        col[i] --;
        dp[i][1<<col[i]] = 1;
    }
    F0R(i,M) {
        int a,b; cin >> a >> b;
        adj[a].pb(b), adj[b].pb(a);
    }
    F0R(i,1<<K) FOR(j,1,N+1) 
        for (int k: adj[j]) if (!(i&(1<<col[k]))) 
            dp[k][i^(1<<col[k])] += dp[j][i];
    
    ll ans = 0;
    FOR(i,1,N+1) F0R(j,1<<K) if (__builtin_popcount(j) > 1) ans += dp[i][j];
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 5 ms 2912 KB Output is correct
3 Correct 5 ms 3096 KB Output is correct
4 Correct 5 ms 3096 KB Output is correct
5 Correct 6 ms 3140 KB Output is correct
6 Correct 5 ms 3204 KB Output is correct
7 Correct 5 ms 3204 KB Output is correct
8 Correct 4 ms 3204 KB Output is correct
9 Correct 4 ms 3204 KB Output is correct
10 Correct 4 ms 3204 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 10944 KB Output is correct
2 Correct 107 ms 11852 KB Output is correct
3 Incorrect 31 ms 34088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 5 ms 2912 KB Output is correct
3 Correct 5 ms 3096 KB Output is correct
4 Correct 5 ms 3096 KB Output is correct
5 Correct 6 ms 3140 KB Output is correct
6 Correct 5 ms 3204 KB Output is correct
7 Correct 5 ms 3204 KB Output is correct
8 Correct 4 ms 3204 KB Output is correct
9 Correct 4 ms 3204 KB Output is correct
10 Correct 4 ms 3204 KB Output is correct
11 Correct 142 ms 10944 KB Output is correct
12 Correct 107 ms 11852 KB Output is correct
13 Incorrect 31 ms 34088 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 6 ms 34088 KB Output is correct
2 Correct 89 ms 34088 KB Output is correct
3 Correct 38 ms 34088 KB Output is correct
4 Correct 232 ms 39748 KB Output is correct
5 Correct 137 ms 41864 KB Output is correct
6 Correct 473 ms 42520 KB Output is correct
7 Correct 60 ms 42520 KB Output is correct
8 Correct 293 ms 44668 KB Output is correct
9 Correct 189 ms 46648 KB Output is correct
10 Correct 228 ms 48140 KB Output is correct
11 Correct 204 ms 48140 KB Output is correct
12 Correct 229 ms 48140 KB Output is correct
13 Correct 196 ms 48140 KB Output is correct
14 Correct 411 ms 52316 KB Output is correct
15 Correct 470 ms 53904 KB Output is correct
16 Correct 6 ms 53904 KB Output is correct
17 Correct 5 ms 53904 KB Output is correct
18 Correct 5 ms 53904 KB Output is correct
19 Correct 5 ms 53904 KB Output is correct
20 Correct 5 ms 53904 KB Output is correct
21 Correct 5 ms 53904 KB Output is correct
22 Correct 4 ms 53904 KB Output is correct
23 Correct 5 ms 53904 KB Output is correct
24 Correct 5 ms 53904 KB Output is correct
25 Correct 6 ms 53904 KB Output is correct