oj.uz

Submission #951752

# Submission time Handle Problem Language Result Execution time Memory
951752 2024-03-22T13:17:37 Z mocha Paths (BOI18_paths) C++14
20 / 100
 80 ms 17484 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15004 KB Output is correct
2 Correct 30 ms 14936 KB Output is correct
3 Correct 76 ms 17220 KB Output is correct
4 Correct 44 ms 12880 KB Output is correct
5 Correct 42 ms 10880 KB Output is correct
6 Correct 60 ms 16796 KB Output is correct
7 Correct 78 ms 17484 KB Output is correct
8 Correct 80 ms 17464 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -