Submission #951752

#	Time	Username	Problem	Language	Result	Execution time	Memory
951752		mocha	Paths (BOI18_paths)	C++14	20 / 100	80 ms	17484 KiB

paths

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mx = 3e5+5;

int n, m, k;
int a[mx];
long long b[6][mx];
long long ans = 0;
long long ans1, ans2, ans3, ans4;

pair<int, int> e[mx];

signed main() {
	cin.tie(0);ios::sync_with_stdio(0);

	cin >> n >> m >> k;
	for (int i=1;i<=n;i++) {
		cin >> a[i];
	}
	for (int i=1;i<=m;i++) {
		int u, v;
		cin >> u >> v;
		b[a[v]][u]++;
		b[a[u]][v]++;
		e[i].first = u;
		e[i].second = v;
	}
	for (int i=1;i<=n;i++) {
		long long tmp = 1;
		long long cnt = 0;
		vector<int> v;
		for (int j=1;j<=k;j++) {
			if (a[i] == j) continue;
			v.push_back(j);
			cnt += b[j][i];
		}
		for (int j=0;j<v.size();j++) {
			for (int k=0;k<v.size();k++) {
				if ( j == k ) continue;
				ans2 += b[v[j]][i] * b[v[k]][i];
			}
		}
		ans1 += cnt;
	}
	if ( k >= 4 ) {
		for (int i=0;i<m;i++) {
			bool arr[6] = {1, 1, 1, 1, 1, 1};
			int u = e[i].first, v = e[i].second;
			if (a[u] == a[v]) continue;
			arr[a[u]] = 0;
			arr[a[v]] = 0;
			vector<int> ve;
			for (int j=1;j<=k;j++) {
				if (arr[j]) {
					ve.push_back(j);
				}
			}
			for (int j=0;j<ve.size();j++) {
				for (int k=0;k<ve.size();k++) {
					if (j == k) continue;
					ans3 += b[ve[j]][u] * b[ve[k]][v] * 2;
				}
			}
		}
	}
	if (k==1) {
		ans = 0;
	} else if (k==2) {
		ans = ans1;
	} else if ( k == 3 ) {
		ans = ans1 + ans2;
	} else if ( k == 4 ) {
		ans = ans1 + ans2 + ans3;
	}
	cout << ans << "\n";
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:38:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int j=0;j<v.size();j++) {
      |                ~^~~~~~~~~
paths.cpp:39:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for (int k=0;k<v.size();k++) {
      |                 ~^~~~~~~~~
paths.cpp:30:13: warning: unused variable 'tmp' [-Wunused-variable]
   30 |   long long tmp = 1;
      |             ^~~
paths.cpp:59:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for (int j=0;j<ve.size();j++) {
      |                 ~^~~~~~~~~~
paths.cpp:60:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int k=0;k<ve.size();k++) {
      |                  ~^~~~~~~~~~

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