oj.uz

Submission #518395

# Submission time Handle Problem Language Result Execution time Memory
518395 2022-01-23T16:00:19 Z Ierus Paths (BOI18_paths) C++14
100 / 100
 458 ms 317484 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 3e5+324;
const int MOD = 1e9+7;
long long res;
int n, m, k, c[N];
vector<int> g[N];
long long cnt[6][N][(1<<5)];
void Count(int v, int x){
	for(auto to : g[v]){
		if(c[to] == c[v]) continue;
		for(int mask = 0; mask < (1 << k); ++mask){
			if(((mask >> c[v]) & 1)) continue;
			cnt[x][v][mask|(1<<c[v])] += cnt[x-1][to][mask];
		};
	};
}
int main(){
	ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++i){
		cin >> c[i]; --c[i];
		cnt[1][i][(1<<c[i])] = 1;
	}
	for(int i = 1; i <= m; ++i){
		int x, y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	for(int x = 2; x <= k; ++x){
		for(int i = 1; i <= n; ++i){
			Count(i, x);
		}
	}
	long long sum = 0;
	for(int x = 2; x <= k; ++x){
		for(int i = 1; i <= n; ++i){
			for(int j = 0;  j < (1 << k); ++j){
				sum += cnt[x][i][j];
			}
		}
	}
	cout << sum;
}

Subtask #1
23.0 / 23.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 14716 KB Output is correct
2 Correct 52 ms 11504 KB Output is correct
3 Correct 324 ms 242336 KB Output is correct
4 Correct 94 ms 26952 KB Output is correct
5 Correct 87 ms 19324 KB Output is correct
6 Correct 223 ms 165528 KB Output is correct
7 Correct 333 ms 242416 KB Output is correct
8 Correct 359 ms 243012 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 3 ms 7500 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7308 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 4 ms 7512 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 3 ms 7500 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct
11 Correct 76 ms 14716 KB Output is correct
12 Correct 52 ms 11504 KB Output is correct
13 Correct 324 ms 242336 KB Output is correct
14 Correct 94 ms 26952 KB Output is correct
15 Correct 87 ms 19324 KB Output is correct
16 Correct 223 ms 165528 KB Output is correct
17 Correct 333 ms 242416 KB Output is correct
18 Correct 359 ms 243012 KB Output is correct
19 Correct 70 ms 14796 KB Output is correct
20 Correct 53 ms 11460 KB Output is correct
21 Correct 345 ms 242276 KB Output is correct
22 Correct 92 ms 26852 KB Output is correct
23 Correct 87 ms 19432 KB Output is correct
24 Correct 275 ms 165532 KB Output is correct
25 Correct 334 ms 242356 KB Output is correct
26 Correct 329 ms 243012 KB Output is correct
27 Correct 67 ms 11716 KB Output is correct
28 Correct 88 ms 19752 KB Output is correct
29 Correct 457 ms 317484 KB Output is correct
30 Correct 287 ms 164024 KB Output is correct
31 Correct 306 ms 164104 KB Output is correct
32 Correct 458 ms 317420 KB Output is correct
33 Correct 4 ms 7372 KB Output is correct
34 Correct 4 ms 7500 KB Output is correct
35 Correct 4 ms 7372 KB Output is correct
36 Correct 4 ms 7372 KB Output is correct
37 Correct 3 ms 7372 KB Output is correct
38 Correct 4 ms 7500 KB Output is correct
39 Correct 4 ms 7372 KB Output is correct
40 Correct 4 ms 7500 KB Output is correct
41 Correct 4 ms 7372 KB Output is correct
42 Correct 4 ms 7372 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 31 ms 9128 KB Output is correct
3 Correct 20 ms 8896 KB Output is correct
4 Correct 117 ms 85700 KB Output is correct
5 Correct 78 ms 86376 KB Output is correct
6 Correct 234 ms 135876 KB Output is correct
7 Correct 25 ms 8908 KB Output is correct
8 Correct 128 ms 110700 KB Output is correct
9 Correct 108 ms 111408 KB Output is correct
10 Correct 121 ms 111392 KB Output is correct
11 Correct 117 ms 72004 KB Output is correct
12 Correct 138 ms 104420 KB Output is correct
13 Correct 120 ms 72072 KB Output is correct
14 Correct 249 ms 135824 KB Output is correct
15 Correct 245 ms 135924 KB Output is correct
16 Correct 4 ms 7372 KB Output is correct
17 Correct 4 ms 7500 KB Output is correct
18 Correct 5 ms 7372 KB Output is correct
19 Correct 4 ms 7412 KB Output is correct
20 Correct 4 ms 7372 KB Output is correct
21 Correct 4 ms 7500 KB Output is correct
22 Correct 4 ms 7372 KB Output is correct
23 Correct 4 ms 7500 KB Output is correct
24 Correct 4 ms 7372 KB Output is correct
25 Correct 4 ms 7424 KB Output is correct