oj.uz

Submission #951975

# Submission time Handle Problem Language Result Execution time Memory
951975 2024-03-23T03:08:52 Z mocha Paths (BOI18_paths) C++14
20 / 100
 69 ms 26296 KB 
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
const int mx = 3e5+5;

int n, m, k;
int cnt[1<<5][mx];
int tmp[1<<5][mx];
int c[mx];
vector<pair<int, int>> e;
int ans1, ans2, ans3, ans4, ans5;
vector<int> nums[6];
int ans;

void init() {
	for (int i=0;i<1<<k;i++) {
		int ii=i, cnt=0;
		while (ii) {
			cnt += (ii&1);
			ii >>= 1;
		}
		nums[cnt].push_back(i);
	}
}

void get1() {
	for (auto [u, v]:e) {
		cnt[c[v]][u]++;
		cnt[c[u]][v]++;
	}
	for (int i=1;i<=n;i++) {
		for (int j:nums[1]) {	
			if (j == c[i]) continue;
			ans1 += cnt[j][i];
		}
	}
}

void get2() {
	for (int i=1;i<=n;i++) {
		for (int x = 1;x<1<<k;x<<=1) {
			if (x == c[i]) continue;
			for (int y = 1; y < 1<<k ; y<<=1) {
				if ( y == c[i] or x == y) continue;
				ans2 += cnt[x][i] * cnt[y][i];
			}
		}
	}
}

void get3() {}
void get4() {}

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

	cin >> n >> m >> k;
	e.resize(m);
	init();
	for (int i=1;i<=n;i++) {
		int x;
		cin >> x; x--;
		c[i] = 1<<x;
	}
	for (int i=0;i<m;i++) {
		cin >> e[i].ff >> e[i].ss;
	}
	if (k == 1) {
		ans = 0;
	} else if (k == 2) {
		get1();
		ans = ans1;
	} else if (k == 3) {
		get1(); get2();
		ans = ans1 + ans2;
	} else if (k == 4) {
		get1(); get3();
		ans = ans1 + ans2 + ans3;
	} 
	cout << ans << "\n";
}

Compilation message

paths.cpp: In function 'void get1()':
paths.cpp:29:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |  for (auto [u, v]:e) {
      |            ^

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8536 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 36 ms 14144 KB Output is correct
2 Correct 33 ms 13396 KB Output is correct
3 Correct 69 ms 26296 KB Output is correct
4 Correct 39 ms 16720 KB Output is correct
5 Correct 37 ms 10576 KB Output is correct
6 Correct 55 ms 21332 KB Output is correct
7 Correct 63 ms 25936 KB Output is correct
8 Correct 62 ms 25940 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8536 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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -