Submission #1287136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287136		g4yuhg	Paths (BOI18_paths)	C++20	53 / 100	161 ms	58996 KiB

paths

#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 100005
#define LOG 17
using namespace std;

const ll inf = 1e9;

ll getbit(ll mask, ll i) {
	return (mask >> i) & 1;
}

ll onbit(ll mask, ll i) {
	return mask | (1 << i);
}

bool ghuy4g;

ll n, m, k;
vector<ll> adj[N];

pii canh[N];

ll d[N][(1 << 5)], c[N], d1[N][(1 << 5)];

void bfs() {
	for (int i = 1; i <= n; i ++) {
		d[i][onbit(0, c[i])] = 1;
	}
	ll ans = 0;
	for (int turn = 2; turn <= k; turn ++) {
		for (int i = 1; i <= n; i ++) {
			for (int mask = 0; mask < (1 << k); mask ++) {
				d1[i][mask] = d[i][mask];
				d[i][mask] = 0;
			}
		}
		for (int i = 1; i <= m; i ++) {
			ll u, v;
			u = canh[i].fi, v = canh[i].se;
			for (int mask = 0; mask < (1 << k); mask ++) {
				// d[v][onbit(mask, c[v])] += d[u][mask];
				if (getbit(mask, c[v]) == 0) {
					/*if (v == 2 && onbit(mask, c[v]) == 3) {
						cout << "here i " << turn << " " << u << " " << d1[u][mask] << " " << d[v][onbit(mask, c[v])] << endl;
					}*/
					d[v][onbit(mask, c[v])] += d1[u][mask];
				}
				if (getbit(mask, c[u]) == 0) {
					/*if (u == 2 && onbit(mask, c[u]) == 3) {
						cout << "here i " << turn << " " << v << " " << d1[v][mask] << " " << d[u][onbit(mask, c[u])] << endl;
					}*/
					d[u][onbit(mask, c[u])] += d1[v][mask];
				}
			}
		}
		for (int i = 1; i <= n; i ++) {
			for (int mask = 0; mask < (1 << k); mask ++) {
				ans += d[i][mask];
				/*if (d[i][mask]) {
					cout << i << " " << bitset<3>(mask) << " " << d[i][mask] << endl;
				}*/
			}
		}
	}
	/*for (int i = 1; i <= n; i ++) {
		for (int mask = 0; mask < (1 << k); mask ++) {
			ans += d[i][mask];
			if (d[i][mask]) {
				cout << i << " " << bitset<3>(mask) << " " << d[i][mask] << endl;
			}
		}
	}*/
	cout << ans << endl;
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
   	cin >> n >> m >> k;
   	for (int i = 1; i <= n; i ++) {
   		cin >> c[i];
   		c[i] -- ;
   	}
   	for (int i = 1; i <= m; i ++) {
   		ll u, v;
   		cin >> u >> v;
   		adj[u].push_back(v);
   		adj[v].push_back(u);
   		canh[i] = {u, v};
   	}
   	bfs();
   	
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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