Submission #538190

#	Time	Username	Problem	Language	Result	Execution time	Memory
538190		new_acc	Paths (BOI18_paths)	C++14	100 / 100	512 ms	56672 KiB

paths

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=3e5+10;
ll dp[1<<5][N];
vi graf[N];
int k[N];
void solve(){
	int n,m,kk;
	cin>>n>>m>>kk;
	for(int i=1;i<=n;i++) cin>>k[i];
	for(int i=1,a,b,c;i<=m;i++){
		cin>>a>>b;
		graf[a].push_back(b),graf[b].push_back(a);
	}
	ll res=0;
	for(int i=1;i<(1<<kk);i++){
		for(int wsk=1;wsk<=n;wsk++){
			if((1<<(k[wsk]-1))&i){
				if(__builtin_popcount(i)==1) dp[i][wsk]=1;
				else for(auto u:graf[wsk]) dp[i][wsk]+=dp[i-(1<<(k[wsk]-1))][u];
			}
			res+=dp[i][wsk];
		}
	}
	cout<<res-n<<"\n";
}
int main(){
	solve();
}

Compilation message (stderr)

paths.cpp: In function 'void solve()':
paths.cpp:17:18: warning: unused variable 'c' [-Wunused-variable]
   17 |  for(int i=1,a,b,c;i<=m;i++){
      |                  ^

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