Submission #951655

#	Time	Username	Problem	Language	Result	Execution time	Memory
951655		mocha	Paths (BOI18_paths)	C++14	0 / 100	39 ms	8020 KiB

paths

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

int n, m, k;
int a[mx];
int b[2][16][105][105];

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

	cin >> n >> m >> k;
	for (int i=1;i<=n;i++) {
		cin >> a[i];a[i]--;
		a[i] = 1 << a[i];
	}
//	for (int i=1;i<=n;i++) {
//		cout << a[i] << " ";
//	}
	for (int i=0;i<m;i++) {
		int u, v;	
		cin >> u >> v;
		if (a[u] == a[v]) continue;
		int col = 0;
		col |= a[u] | a[v];
		b[0][col][u][v]++;
		b[0][col][v][u]++;
//		cout << u << " " << v << "\n";
	}
	for (int i=1;i<=n;i++) {
		b[0][a[i]][i][i]++;
	}
	for (int x=0;x<1<<k;x++) {
		int xx = x;
		int cnt = 0;
//		while (xx) {
//			cout << (xx&1);
//			xx>>=1;
//		}
//		cout << '\n';
//		for (int i=1;i<=n;i++) {
//			for (int j=1;j<=n;j++) {
//				cout << b[0][x][i][j] << " ";
//			}
//			cout << "\n";
//		}
//		cout << "\n";
	}
//	for (int i=0;i<30;i++) cout << '-';
//	cout << '\n';
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			for (int k=1;k<=n;k++) {
				for (int x = 1; x<1<<k;x++) {
					b[i&1][x][j][k] = b[~i&1][x][j][k];
				}
			}
		}
		for (int x = 0; x<1<<k;x++) {
			if (x & a[i]) continue;
			for (int y = 0; y<1<<k; y++) {
				if (y & a[i]) continue;
				if (y & x) continue;
				int xx = x, yy = y;
//				while (xx) {
//					cout << (xx&1);
//					xx >>= 1;
//				}
//				cout << " ";
//				while (yy) {
//					cout << (yy&1);
//					yy >>= 1;
//				}
//				cout << "\n";
				for (int j=1;j<=n;j++) {
					for (int k=1;k<=n;k++) {
//						cout << i << " " << x << " " << y << " " << j << " " << k << "\n";
						int tmp = 
							b[~i&1][x][j][i] * 
							b[~i&1][y][i][k];
//						if (tmp) {
//							cout << "owo\n";
//						}
						b[i&1][x&y&a[i]][j][k] += tmp;
					}
				}
			}
		}
	}
	long long sum = 0;
	for (int x = 1; x < 1<<k ; x++) {
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=n;j++) {
//				cout << b[n&1][x][i][j] << " ";
				sum += b[n&1][x][i][j];
			}
//			cout << "\n";
		}
//		cout << "\n";
	}
	cout << sum << "\n";
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:34:7: warning: unused variable 'xx' [-Wunused-variable]
   34 |   int xx = x;
      |       ^~
paths.cpp:35:7: warning: unused variable 'cnt' [-Wunused-variable]
   35 |   int cnt = 0;
      |       ^~~
paths.cpp:64:9: warning: unused variable 'xx' [-Wunused-variable]
   64 |     int xx = x, yy = y;
      |         ^~
paths.cpp:64:17: warning: unused variable 'yy' [-Wunused-variable]
   64 |     int xx = x, yy = y;
      |                 ^~

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