Submission #716410

#	Time	Username	Problem	Language	Result	Execution time	Memory
716410		ajab_01	Paths (BOI18_paths)	C++17	43 / 100	3070 ms	27716 KiB

paths

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 3e5 + 5;
vector<pair<int , int> > edge;
vector<int> g[N];
int C[N] , n , m , k;
int ans;

void cal2(){
	for(auto i : edge){
		int u = i.first , v = i.second;
		if(C[u] != C[v])
			ans++;
	}
}

void cal3(){
	for(int i = 1 ; i <= n ; i++){
		int cnt[6];
		memset(cnt , 0 , sizeof(cnt));
		for(int j : g[i]){
			if(C[j] == C[i]) continue;
			cnt[C[j]]++;
		}
		for(int i = 1 ; i <= 5 ; i++)
			for(int j = i + 1 ; j <= 5 ; j++)
				ans += cnt[i] * cnt[j];
	}
}

void cal4(){
	for(auto i : edge){
		int u = i.first , v = i.second;
		if(C[u] == C[v]) continue;
		int cnt1[6] , mx = 0;
		memset(cnt1 , 0 , sizeof(cnt1));
		for(int j : g[u]){
			if(C[j] == C[u] || C[j] == C[v]) continue;
			cnt1[C[j]]++;
		}
		int cnt2[6];
		memset(cnt2 , 0 , sizeof(cnt2));
		for(int j : g[v]){
			if(C[j] == C[u] || C[j] == C[v]) continue;
			cnt2[C[j]]++;
		}
		for(int i = 1 ; i <= 5 ; i++){
			for(int j = i + 1 ; j <= 5 ; j++){
				ans += cnt1[i] * cnt2[j];
				ans += cnt1[j] * cnt2[i];
			}
		}
	}
}

int32_t main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1 ; i <= n ; i++)
		cin >> C[i];

	for(int i = 1 ; i <= m ; i++){
		int u , v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		edge.push_back({u , v});
	}

	if(k == 1){
		cout << ans * 2 << '\n';
		return 0;
	}

	cal2();

	if(k == 2){
		cout << ans * 2 << '\n';
		return 0;
	}

	cal3();

	if(k == 3){
		cout << ans * 2 << '\n';
		return 0;
	}

	cal4();

	if(k == 4){
		cout << ans * 2 << '\n';
		return 0;
	}

	// cal5();

	// cout << ans * 2 << '\n';
	return 0;
}

Compilation message (stderr)

paths.cpp: In function 'void cal4()':
paths.cpp:38:17: warning: unused variable 'mx' [-Wunused-variable]
   38 |   int cnt1[6] , mx = 0;
      |                 ^~

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