Submission #100155

#	Time	Username	Problem	Language	Result	Execution time	Memory
100155		tushar_2658	Paths (BOI18_paths)	C++14	100 / 100	708 ms	172544 KiB

paths

#include "bits/stdc++.h"
using namespace std;


using ll = long long;
const int maxn = 3e5 + 5;
int arr[maxn];
vector<int> edges[maxn];
int n, m, k;
ll dp[1 << 6][maxn];

ll call(int mask, int node){
	if(dp[mask][node] != -1)return dp[mask][node];
	int ans = 1;
	for(auto i : edges[node]){
		if((mask >> arr[i]) & 1)continue;
		else {
			ans += call(mask ^ (1 << arr[i]), i);
		}
	}return dp[mask][node] = ans;
}

int main(){
	scanf("%d %d %d", &n, &m, &k);
	for(int i=1; i<=n; i++){
		scanf("%d", &arr[i]);
		//--arr[i];
	}
	for(int i=1; i<=m; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		edges[x].emplace_back(y); 
		edges[y].emplace_back(x);
	}
	memset(dp, -1, sizeof dp);
	ll ans = 0, mask = 0;
	for(int i=1; i<=n; i++){
		ans += call((mask ^ (1 << arr[i])), i);
	}cout<<ans-n<<endl;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~
paths.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

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