Submission #951991

#	Time	Username	Problem	Language	Result	Execution time	Memory
951991		mocha	Paths (BOI18_paths)	C++14	70 / 100	82 ms	33756 KiB

paths

#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() {
	for (auto [u, v]:e) {
		if (c[u] == c[v]) continue;
		for (int x = 1;x<1<<k;x<<=1) {
			if (x == c[u] or x == c[v]) continue;
			for (int y = 1; y < 1<<k ; y<<=1) {
				if (y == c[u] or y == c[v] or x == y) continue;
				ans2 += cnt[x][v] * cnt[y][u] * 2;
			}
		}
	}
}

void get4() {
	for (auto [u, v]:e) {	
		if (c[u] == c[v]) return;
		for (int i=1;i<1<<k;i<<=1) {
			if (i != c[u] and i != c[v]) {
				cnt[i|c[u]][v] += cnt[i][u];
				cnt[i|c[v]][u] += cnt[i][v];
			}
		}
	}
	int mask = 1<<5;
	mask--;
	for (int i=1;i<=n;i++) {
		for (int j:nums[2]) {
			if (j & c[i]) continue;
			int inv = (~(j&c[i])) & mask;
			ans3 += cnt[j][i] * cnt[inv][i] * 2;
		}
	}
}

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(); get2(); get3();
		ans = ans1 + ans2 + ans3;
	} else {
		get1(); get2(); get3(); get4();
		ans = ans1 + ans2 + ans3 + ans4;
	}
	cout << ans << "\n";
}

Compilation message (stderr)

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) {
      |            ^
paths.cpp: In function 'void get3()':
paths.cpp:54:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |  for (auto [u, v]:e) {
      |            ^
paths.cpp: In function 'void get4()':
paths.cpp:67:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |  for (auto [u, v]:e) {
      |            ^

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