oj.uz

Submission #797916

# Submission time Handle Problem Language Result Execution time Memory
797916 2023-07-30T06:58:13 Z sentheta Paths (BOI18_paths) C++17
100 / 100
 318 ms 100388 KB 
// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

#define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}












const int N = 3e5+5;
const int K = 5;

int n, m, k;
int a[N];
V<int> adj[N];

int dp[N][1<<K];

void solve(){
	
	cin >> n >> m >> k;
	
	rep(x,1,n+1){
		cin >> a[x];
		a[x]--;
		
		dp[x][1<<a[x]] = 1;
	}
	
	rep(i,0,m){
		int u, v;
		cin >> u >> v;
		
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	int ans = 0;
	rep(msk,0,1<<k) if(bitcnt(msk)>=2){
		rep(x,1,n+1) if(msk&1<<a[x]){
			for(int y : adj[x]){
				dp[x][msk] += dp[y][msk^1<<a[x]];
			}
			
			ans += dp[x][msk];
		}
	}
	
	cout << ans << nl;	
	
	
}

Subtask #1
23.0 / 23.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 18636 KB Output is correct
2 Correct 38 ms 16936 KB Output is correct
3 Correct 237 ms 99856 KB Output is correct
4 Correct 67 ms 26572 KB Output is correct
5 Correct 88 ms 26528 KB Output is correct
6 Correct 164 ms 71932 KB Output is correct
7 Correct 245 ms 99828 KB Output is correct
8 Correct 256 ms 100292 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7380 KB Output is correct
2 Correct 3 ms 7376 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7388 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 4 ms 7388 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7384 KB Output is correct
11 Correct 49 ms 18636 KB Output is correct
12 Correct 38 ms 16936 KB Output is correct
13 Correct 237 ms 99856 KB Output is correct
14 Correct 67 ms 26572 KB Output is correct
15 Correct 88 ms 26528 KB Output is correct
16 Correct 164 ms 71932 KB Output is correct
17 Correct 245 ms 99828 KB Output is correct
18 Correct 256 ms 100292 KB Output is correct
19 Correct 58 ms 18644 KB Output is correct
20 Correct 49 ms 16888 KB Output is correct
21 Correct 273 ms 99856 KB Output is correct
22 Correct 88 ms 26632 KB Output is correct
23 Correct 82 ms 26620 KB Output is correct
24 Correct 135 ms 71996 KB Output is correct
25 Correct 270 ms 99828 KB Output is correct
26 Correct 208 ms 100388 KB Output is correct
27 Correct 40 ms 16912 KB Output is correct
28 Correct 59 ms 20828 KB Output is correct
29 Correct 318 ms 99856 KB Output is correct
30 Correct 180 ms 58808 KB Output is correct
31 Correct 177 ms 58968 KB Output is correct
32 Correct 291 ms 99972 KB Output is correct
33 Correct 4 ms 7380 KB Output is correct
34 Correct 3 ms 7296 KB Output is correct
35 Correct 3 ms 7380 KB Output is correct
36 Correct 3 ms 7380 KB Output is correct
37 Correct 3 ms 7380 KB Output is correct
38 Correct 3 ms 7384 KB Output is correct
39 Correct 3 ms 7380 KB Output is correct
40 Correct 3 ms 7380 KB Output is correct
41 Correct 3 ms 7380 KB Output is correct
42 Correct 3 ms 7380 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 17 ms 10340 KB Output is correct
3 Correct 15 ms 10452 KB Output is correct
4 Correct 55 ms 38060 KB Output is correct
5 Correct 48 ms 38728 KB Output is correct
6 Correct 113 ms 37988 KB Output is correct
7 Correct 16 ms 10340 KB Output is correct
8 Correct 77 ms 37980 KB Output is correct
9 Correct 58 ms 38480 KB Output is correct
10 Correct 66 ms 38616 KB Output is correct
11 Correct 58 ms 24004 KB Output is correct
12 Correct 74 ms 31216 KB Output is correct
13 Correct 59 ms 24376 KB Output is correct
14 Correct 118 ms 38072 KB Output is correct
15 Correct 116 ms 38152 KB Output is correct
16 Correct 3 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 3 ms 7384 KB Output is correct
19 Correct 3 ms 7380 KB Output is correct
20 Correct 3 ms 7380 KB Output is correct
21 Correct 3 ms 7380 KB Output is correct
22 Correct 3 ms 7412 KB Output is correct
23 Correct 3 ms 7380 KB Output is correct
24 Correct 4 ms 7380 KB Output is correct
25 Correct 4 ms 7380 KB Output is correct