oj.uz

Submission #518381

# Submission time Handle Problem Language Result Execution time Memory
518381 2022-01-23T15:53:06 Z Ierus Paths (BOI18_paths) C++17
100 / 100
 658 ms 331388 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[7][N][33];
void Count(int v, int x){
	for(auto to : g[v]){
		if(c[to] == c[v]) continue;
//		cerr << "to: " << to << "\n"; 
		for(int mask = 0; mask < (1 << k); ++mask){
			if(((mask >> c[v]) & 1)) continue;
//			cerr  << mask << " <-> "<< (mask|(1<<c[v])) << " -> " << cnt[x-1][to][mask] << "\n";
			cnt[x][v][mask|(1<<c[v])] += cnt[x-1][to][mask];
		};
	};
}
void go(int x){
	for(int i = 1; i <= n; ++i){
//		cerr << "count(" << i << "," << x << ")\n";
		Count(i, x);
	}
}
int main(){
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++i){
		cin >> c[i];
		--c[i];
		cnt[1][i][(1<<c[i])] = 1;
//		cerr << cnt[1][i][(1<<c[i])] << '\n';
	}
	for(int i = 1; i <= m; ++i){
		int x, y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
//	cerr << "1<<k: " << (1 << k) << '\n';
	for(int i = 2; i <= k; ++i){
//		cerr << "k -> " << i << "\n";
		go(i);
	}
	long long sum = 0;
	for(int kk = 1; kk <= k; ++kk){
//		cerr << "K: " << kk << "\n";
		for(int i = 1; i <= n; ++i){
			long long sm = 0;
			for(int j = 0;  j < (1 << k); ++j){
				sm += cnt[kk][i][j];
			}
			sum += sm;
//			cerr << i << " -> " << sm << "\n";
		}
	}
	cout << sum - n;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7384 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 5 ms 7384 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 4 ms 7500 KB Output is correct
9 Correct 5 ms 7384 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 167 ms 17676 KB Output is correct
2 Correct 157 ms 13848 KB Output is correct
3 Correct 519 ms 253840 KB Output is correct
4 Correct 238 ms 30720 KB Output is correct
5 Correct 186 ms 22908 KB Output is correct
6 Correct 371 ms 174256 KB Output is correct
7 Correct 513 ms 253852 KB Output is correct
8 Correct 531 ms 254484 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 5 ms 7384 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 5 ms 7384 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Correct 4 ms 7500 KB Output is correct
9 Correct 5 ms 7384 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct
11 Correct 167 ms 17676 KB Output is correct
12 Correct 157 ms 13848 KB Output is correct
13 Correct 519 ms 253840 KB Output is correct
14 Correct 238 ms 30720 KB Output is correct
15 Correct 186 ms 22908 KB Output is correct
16 Correct 371 ms 174256 KB Output is correct
17 Correct 513 ms 253852 KB Output is correct
18 Correct 531 ms 254484 KB Output is correct
19 Correct 185 ms 17736 KB Output is correct
20 Correct 139 ms 13760 KB Output is correct
21 Correct 484 ms 253804 KB Output is correct
22 Correct 218 ms 30768 KB Output is correct
23 Correct 205 ms 23004 KB Output is correct
24 Correct 421 ms 174268 KB Output is correct
25 Correct 517 ms 253776 KB Output is correct
26 Correct 564 ms 254628 KB Output is correct
27 Correct 149 ms 14024 KB Output is correct
28 Correct 183 ms 22836 KB Output is correct
29 Correct 654 ms 331388 KB Output is correct
30 Correct 478 ms 172892 KB Output is correct
31 Correct 482 ms 172736 KB Output is correct
32 Correct 658 ms 331336 KB Output is correct
33 Correct 4 ms 7376 KB Output is correct
34 Correct 4 ms 7488 KB Output is correct
35 Correct 4 ms 7376 KB Output is correct
36 Correct 4 ms 7376 KB Output is correct
37 Correct 4 ms 7364 KB Output is correct
38 Correct 6 ms 7488 KB Output is correct
39 Correct 5 ms 7376 KB Output is correct
40 Correct 4 ms 7376 KB Output is correct
41 Correct 4 ms 7364 KB Output is correct
42 Correct 4 ms 7376 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7356 KB Output is correct
2 Correct 64 ms 9812 KB Output is correct
3 Correct 45 ms 9544 KB Output is correct
4 Correct 149 ms 89328 KB Output is correct
5 Correct 144 ms 90048 KB Output is correct
6 Correct 269 ms 141032 KB Output is correct
7 Correct 53 ms 9800 KB Output is correct
8 Correct 194 ms 115140 KB Output is correct
9 Correct 209 ms 115900 KB Output is correct
10 Correct 195 ms 115760 KB Output is correct
11 Correct 152 ms 75016 KB Output is correct
12 Correct 187 ms 108596 KB Output is correct
13 Correct 185 ms 75228 KB Output is correct
14 Correct 249 ms 141028 KB Output is correct
15 Correct 262 ms 141116 KB Output is correct
16 Correct 4 ms 7376 KB Output is correct
17 Correct 5 ms 7504 KB Output is correct
18 Correct 4 ms 7376 KB Output is correct
19 Correct 5 ms 7340 KB Output is correct
20 Correct 4 ms 7376 KB Output is correct
21 Correct 4 ms 7504 KB Output is correct
22 Correct 4 ms 7376 KB Output is correct
23 Correct 5 ms 7484 KB Output is correct
24 Correct 4 ms 7376 KB Output is correct
25 Correct 4 ms 7376 KB Output is correct