답안 #59155 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59155	2018-07-20T19:53:55 Z	Benq	Paths (BOI18_paths)	C++14	100 / 100	1639 ms	167776 KB

paths

#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 = 300001;

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

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	7416 KB	Output is correct
2	Correct	10 ms	7416 KB	Output is correct
3	Correct	9 ms	7608 KB	Output is correct
4	Correct	9 ms	7608 KB	Output is correct
5	Correct	10 ms	7608 KB	Output is correct
6	Correct	10 ms	7652 KB	Output is correct
7	Correct	10 ms	7652 KB	Output is correct
8	Correct	8 ms	7652 KB	Output is correct
9	Correct	9 ms	7652 KB	Output is correct
10	Correct	9 ms	7652 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	117 ms	12444 KB	Output is correct
2	Correct	96 ms	12444 KB	Output is correct
3	Correct	1012 ms	96460 KB	Output is correct
4	Correct	306 ms	96460 KB	Output is correct
5	Correct	284 ms	96460 KB	Output is correct
6	Correct	510 ms	96460 KB	Output is correct
7	Correct	1002 ms	111800 KB	Output is correct
8	Correct	958 ms	116892 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	7416 KB	Output is correct
2	Correct	10 ms	7416 KB	Output is correct
3	Correct	9 ms	7608 KB	Output is correct
4	Correct	9 ms	7608 KB	Output is correct
5	Correct	10 ms	7608 KB	Output is correct
6	Correct	10 ms	7652 KB	Output is correct
7	Correct	10 ms	7652 KB	Output is correct
8	Correct	8 ms	7652 KB	Output is correct
9	Correct	9 ms	7652 KB	Output is correct
10	Correct	9 ms	7652 KB	Output is correct
11	Correct	117 ms	12444 KB	Output is correct
12	Correct	96 ms	12444 KB	Output is correct
13	Correct	1012 ms	96460 KB	Output is correct
14	Correct	306 ms	96460 KB	Output is correct
15	Correct	284 ms	96460 KB	Output is correct
16	Correct	510 ms	96460 KB	Output is correct
17	Correct	1002 ms	111800 KB	Output is correct
18	Correct	958 ms	116892 KB	Output is correct
19	Correct	150 ms	116892 KB	Output is correct
20	Correct	97 ms	116892 KB	Output is correct
21	Correct	1002 ms	126068 KB	Output is correct
22	Correct	235 ms	126068 KB	Output is correct
23	Correct	148 ms	126068 KB	Output is correct
24	Correct	653 ms	126068 KB	Output is correct
25	Correct	872 ms	141296 KB	Output is correct
26	Correct	912 ms	146500 KB	Output is correct
27	Correct	123 ms	146500 KB	Output is correct
28	Correct	193 ms	146500 KB	Output is correct
29	Correct	1519 ms	155384 KB	Output is correct
30	Correct	775 ms	155384 KB	Output is correct
31	Correct	823 ms	155384 KB	Output is correct
32	Correct	1639 ms	167776 KB	Output is correct
33	Correct	11 ms	167776 KB	Output is correct
34	Correct	11 ms	167776 KB	Output is correct
35	Correct	10 ms	167776 KB	Output is correct
36	Correct	9 ms	167776 KB	Output is correct
37	Correct	10 ms	167776 KB	Output is correct
38	Correct	9 ms	167776 KB	Output is correct
39	Correct	10 ms	167776 KB	Output is correct
40	Correct	8 ms	167776 KB	Output is correct
41	Correct	8 ms	167776 KB	Output is correct
42	Correct	8 ms	167776 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	167776 KB	Output is correct
2	Correct	78 ms	167776 KB	Output is correct
3	Correct	43 ms	167776 KB	Output is correct
4	Correct	208 ms	167776 KB	Output is correct
5	Correct	149 ms	167776 KB	Output is correct
6	Correct	532 ms	167776 KB	Output is correct
7	Correct	56 ms	167776 KB	Output is correct
8	Correct	296 ms	167776 KB	Output is correct
9	Correct	191 ms	167776 KB	Output is correct
10	Correct	253 ms	167776 KB	Output is correct
11	Correct	205 ms	167776 KB	Output is correct
12	Correct	232 ms	167776 KB	Output is correct
13	Correct	232 ms	167776 KB	Output is correct
14	Correct	457 ms	167776 KB	Output is correct
15	Correct	450 ms	167776 KB	Output is correct
16	Correct	8 ms	167776 KB	Output is correct
17	Correct	8 ms	167776 KB	Output is correct
18	Correct	8 ms	167776 KB	Output is correct
19	Correct	9 ms	167776 KB	Output is correct
20	Correct	9 ms	167776 KB	Output is correct
21	Correct	9 ms	167776 KB	Output is correct
22	Correct	9 ms	167776 KB	Output is correct
23	Correct	9 ms	167776 KB	Output is correct
24	Correct	8 ms	167776 KB	Output is correct
25	Correct	8 ms	167776 KB	Output is correct

답안 #59155

Compilation message

Subtask #1 23.0 / 23.0

Subtask #2 20.0 / 20.0

Subtask #3 27.0 / 27.0

Subtask #4 30.0 / 30.0

Subtask #1
23.0 / 23.0

Subtask #2
20.0 / 20.0

Subtask #3
27.0 / 27.0

Subtask #4
30.0 / 30.0