Submission #952054

#	Time	Username	Problem	Language	Result	Execution time	Memory
952054		mocha	Paths (BOI18_paths)	C++14	100 / 100	80 ms	42768 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 print(int x) {
	while (x) {
		cout << (x&1);
		x>>=1;
	}
	cout << "\n";
}

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=1;j<1<<k;j<<=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;
				int tmp = cnt[x][i] * cnt[y][i];
				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;
				ans3 += cnt[x][v] * cnt[y][u] * 2;
			}
		}
	}
}

void get4() {
	for (auto [u, v]:e) {	
		if (c[u] == c[v]) continue;
		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;
			ans4 += cnt[j][i] * cnt[inv][i];
		}
	}
}


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:37:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |  for (auto [u, v]:e) {
      |            ^
paths.cpp: In function 'void get2()':
paths.cpp:55:9: warning: unused variable 'tmp' [-Wunused-variable]
   55 |     int tmp = cnt[x][i] * cnt[y][i];
      |         ^~~
paths.cpp: In function 'void get3()':
paths.cpp:63:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |  for (auto [u, v]:e) {
      |            ^
paths.cpp: In function 'void get4()':
paths.cpp:76:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |  for (auto [u, v]:e) {
      |            ^

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