제출 #927173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927173		vjudge1	Paths (BOI18_paths)	C++17	100 / 100	359 ms	61276 KiB

paths

#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 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30