oj.uz

답안 #927338

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
927338 2024-02-14T18:30:18 Z pragmatist Paths (BOI18_paths) C++17
100 / 100
 389 ms 64296 KB 
#include<bits/stdc++.h>

using namespace std;


const int N = (int)3e5+3;
const int MOD = (int)1e6+3;
const int B1 = 450;
const int B2 = 450;

int n, m, k, a[N], kol[6];
vector<int> g[N];
bool used[6];
long long ans;

void dfs(int v) {
	used[a[v]] = 1;
	ans++;
	for(auto to : g[v]) {
		if(!used[a[to]]) {
			dfs(to);
		}
	}
	used[a[v]] = 0;
}

int cnt[N][32];
int bb[N][6];
int oo[6][32];
int cc[6][6];

int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i]--;
	}
	for(int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		if(a[u] == a[v]) {
			continue;
		}
		ans += 2;
		bb[u][a[v]]++;
		bb[v][a[u]]++;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 1; i <= n; ++i) {
		int cur = 0;
		memset(kol, 0, sizeof(kol));
		for(auto x : g[i]) {
			ans += 2*(cur-kol[a[x]]);
			cur++;	
			kol[a[x]]++;
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int mask = 0; mask < (1 << k); ++mask) {
			for(int j : g[i]) {
				if(!(mask >> a[j] & 1)) {
					continue;
				}		
				cnt[i][mask]++;
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		memset(oo, 0, sizeof(oo));
		memset(kol, 0, sizeof(kol));
		for(int j : g[i]) {
			kol[a[j]]++;
			for(int mask = 0; mask < (1 << k); ++mask) {
				oo[a[j]][mask] += cnt[j][mask];
			}
		}
		for(int c = 0; c < k; ++c) {
			if(c == a[i]) {
				continue;
			}
			for(int d = 0; d < k; ++d) {
				if(d == a[i] || d == c) {
					continue;
				}	
				int can = (1 << k)-1;
				can ^= (1 << a[i]);
		        can ^= (1 << c);
		        can ^= (1 << d);
		        ans += 1ll*oo[c][can]*kol[d];
			}
		}
	}

	for(int i = 1; i <= n; ++i) {
		memset(oo, 0, sizeof(oo));
		memset(kol, 0, sizeof(kol));
		memset(cc, 0, sizeof(cc));
		for(int j : g[i]) {
			kol[a[j]]++;
			for(int c = 0; c < k; ++c) {
				cc[a[j]][c] += bb[j][c];
			}
			for(int mask = 0; mask < (1 << k); ++mask) {
				oo[a[j]][mask] += cnt[j][mask];
			}
		}
		for(int c = 0; c < k; ++c) {
			if(c == a[i]) {
				continue;
			}
			for(int d = 0; d < k; ++d) {
				if(d == a[i] || d == c) {
					continue;
				}	
				for(int e = 0; e < k; ++e) {
					if(e == d || e == c || e == a[i]) {
						continue;
					}
					for(int f = 0; f < k; ++f) {
						if(f == e || f == d || f == c || f == a[i]) {
							continue;
						}
						ans += 1ll*cc[c][e]*cc[d][f];
					}                                          
				}
			}
		}
	}
	cout << ans;
    return 0;
}

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 2 ms 10904 KB Output is correct
4 Correct 3 ms 10684 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 3 ms 11100 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10916 KB Output is correct
9 Correct 3 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 15188 KB Output is correct
2 Correct 50 ms 14016 KB Output is correct
3 Correct 299 ms 62836 KB Output is correct
4 Correct 67 ms 21816 KB Output is correct
5 Correct 42 ms 10832 KB Output is correct
6 Correct 189 ms 50552 KB Output is correct
7 Correct 371 ms 62832 KB Output is correct
8 Correct 290 ms 63616 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 2 ms 10904 KB Output is correct
4 Correct 3 ms 10684 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 3 ms 11100 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10916 KB Output is correct
9 Correct 3 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 68 ms 15188 KB Output is correct
12 Correct 50 ms 14016 KB Output is correct
13 Correct 299 ms 62836 KB Output is correct
14 Correct 67 ms 21816 KB Output is correct
15 Correct 42 ms 10832 KB Output is correct
16 Correct 189 ms 50552 KB Output is correct
17 Correct 371 ms 62832 KB Output is correct
18 Correct 290 ms 63616 KB Output is correct
19 Correct 60 ms 15268 KB Output is correct
20 Correct 50 ms 14164 KB Output is correct
21 Correct 284 ms 62740 KB Output is correct
22 Correct 62 ms 21584 KB Output is correct
23 Correct 50 ms 10832 KB Output is correct
24 Correct 178 ms 50552 KB Output is correct
25 Correct 309 ms 62964 KB Output is correct
26 Correct 320 ms 63448 KB Output is correct
27 Correct 74 ms 15568 KB Output is correct
28 Correct 85 ms 17816 KB Output is correct
29 Correct 379 ms 64220 KB Output is correct
30 Correct 201 ms 42184 KB Output is correct
31 Correct 233 ms 42364 KB Output is correct
32 Correct 389 ms 64296 KB Output is correct
33 Correct 2 ms 10904 KB Output is correct
34 Correct 3 ms 10844 KB Output is correct
35 Correct 2 ms 10844 KB Output is correct
36 Correct 2 ms 10844 KB Output is correct
37 Correct 2 ms 8796 KB Output is correct
38 Correct 2 ms 10672 KB Output is correct
39 Correct 2 ms 10840 KB Output is correct
40 Correct 2 ms 10844 KB Output is correct
41 Correct 3 ms 10844 KB Output is correct
42 Correct 2 ms 10844 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 47 ms 12504 KB Output is correct
3 Correct 18 ms 12772 KB Output is correct
4 Correct 59 ms 31052 KB Output is correct
5 Correct 50 ms 31188 KB Output is correct
6 Correct 130 ms 31312 KB Output is correct
7 Correct 26 ms 12892 KB Output is correct
8 Correct 80 ms 31312 KB Output is correct
9 Correct 70 ms 31436 KB Output is correct
10 Correct 89 ms 32200 KB Output is correct
11 Correct 81 ms 22076 KB Output is correct
12 Correct 102 ms 25420 KB Output is correct
13 Correct 73 ms 22000 KB Output is correct
14 Correct 119 ms 31496 KB Output is correct
15 Correct 127 ms 31572 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10672 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 8796 KB Output is correct
21 Correct 2 ms 10676 KB Output is correct
22 Correct 2 ms 10840 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct