Submission #914289

#	Time	Username	Problem	Language	Result	Execution time	Memory
914289		dsyz	Paths (BOI18_paths)	C++17	0 / 100	168 ms	24712 KiB

paths

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (300005)
ll N,M,K;
vector<ll> v[MAXN];
ll colour[MAXN], cnt[MAXN][(1ll<<5) + 1];
bool visited[MAXN][(1ll<<5) + 1];
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>M>>K;
	for(ll i = 0;i < N;i++){
		cin>>colour[i];
	}
	for(ll i = 0;i < M;i++){
		ll a,b;
		cin>>a>>b;
		a--, b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	ll ans = 0;
	queue<pair<ll,ll> > q; //node x, colours visited
	for(ll i = 0;i < N;i++){
		if(visited[i][1ll<<colour[i]]) continue;
		q.push({i,1ll<<colour[i]});
		cnt[i][1ll<<colour[i]] = 1;
		ans++;
		visited[i][1ll<<colour[i]] = 1;
		while(!q.empty()){
			ll x = q.front().first;
			ll bitsdone = q.front().second;
			q.pop();
			visited[x][bitsdone] = 1;
			for(auto u : v[x]){
				for(ll bitmask = 0;bitmask < (1ll<<5);bitmask++){
					if(visited[u][bitmask] == 1 && (bitmask & bitsdone) == 0){
						ans += (cnt[x][bitsdone] * cnt[u][bitmask]);
					}
				}
				if((bitsdone & (1ll<<colour[u])) == 0 && !visited[u][bitsdone | (1ll<<colour[u])]){
					q.push({u,bitsdone | (1ll<<colour[u])});
					cnt[u][bitsdone | (1ll<<colour[u])] += cnt[x][bitsdone];
					visited[u][bitsdone | (1ll<<colour[u])] = 1;
				}
			}
		}
	}
	cout<<ans<<'\n';
}

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