제출 #1288563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288563		Jawad_Akbar_JJ	Paths (BOI18_paths)	C++20	70 / 100	290 ms	62876 KiB

paths

#include <iostream>
#include <vector>

using namespace std;
#define int long long
const int N = 1<<19;
int a[N], b[N], c[N], adj[N][17], cnt[50];
vector<int> nei[N];

int getKequal2(int n, int m, int Ans = 0){
	for (int i=1;i<=m;i++)
		Ans += (c[a[i]] != c[b[i]]);
	return Ans * 2;
}

int getKequal3(int n, int m, int Ans = 0){
	for (int i=1;i<=n;i++){
		for (int c1 : {1, 2, 4, 8, 16}){
			for (int c2 : {1, 2, 4, 8, 16}){
				if (c1 == c2 or c1 == c[i] or c2 == c[i])
					continue;
				Ans += adj[i][c1] * adj[i][c2];
			}
		}
	}
	return Ans;
}


int getKequal4(int n, int m, int Ans = 0){
	for (int i=1;i<=m;i++){
		if (c[a[i]] == c[b[i]])
			continue;
		for (int c1 : {1, 2, 4, 8, 16}){
			for (int c2 : {1, 2, 4, 8, 16}){
				if (c1 == c2 or c1 == c[a[i]] or c1 == c[b[i]] or c2 == c[a[i]] or c2 == c[b[i]])
					continue;
				Ans += adj[a[i]][c1] * adj[b[i]][c2];
			}
		}
	}
	return Ans * 2;
}

int getKequal5(int n, int m, int Ans = 0){
	for (int u=1;u<=n;u++){
		for (int j=1;j<32;j++)
			cnt[j] = 0;

		for (int i : nei[u]){
			for (int j : {1, 2, 4, 8, 16})
				if (j != c[u] and j != c[i])
					Ans += cnt[31 - c[i] - j] * adj[i][j];
		}

		for (int i : nei[u]){
			for (int j : {1, 2, 4, 8, 16})
				if (j != c[i] and j != c[u])
					cnt[c[u] | c[i] | j] += adj[i][j];
		}
	}
	return Ans;
}


signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, k, Ans = 0;
	cin>>n>>m>>k;

	for (int i=1;i<=n;i++)
		cin>>c[i], c[i]--, c[i] = 1<<c[i];

	for (int i=1;i<=m;i++){
		cin>>a[i]>>b[i];
		
		if (c[a[i]] == c[b[i]])
			continue;

		adj[a[i]][c[b[i]]]++;
		adj[b[i]][c[a[i]]]++;
		nei[a[i]].push_back(b[i]);
		nei[b[i]].push_back(a[i]);
	}

	Ans += getKequal2(n, m) * (k >= 2);
	Ans += getKequal3(n, m) * (k >= 3);
	Ans += getKequal4(n, m) * (k >= 4);
	Ans += getKequal5(n, m) * (k >= 5);

	cout<<Ans<<'\n';
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 0 / 30