oj.uz

Submission #914289

# Submission time Handle Problem Language Result Execution time Memory
914289 2024-01-21T14:24:53 Z dsyz Paths (BOI18_paths) C++17
0 / 100
 168 ms 24712 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 24712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12712 KB Output isn't correct
2 Halted 0 ms 0 KB -