Submission #69777

#	Time	Username	Problem	Language	Result	Execution time	Memory
69777		MrTEK	Paths (BOI18_paths)	C++14	100 / 100	1463 ms	542216 KiB

paths

#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left isc+isc
#define right isc+isc+1
#define mid (l+r)/2
#define FAfi_IO ios_base::sync_with_fidio(false);
#define escl '\n'

typedef long long int ll;

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 3e5 + 5;
const int M = 5;
const int SQ = 350;
const int MOD = 998244353;

typedef long long int lli;
typedef pair<int,int> pii;

vector <int> ed[N];

int n,m,k,col[N];
long long ans,dp[N][1 << 5][6];

int main() {
	scanf("%d %d %d",&n,&m,&k);
	for (int i = 1 ; i <= n ; i++) {
		scanf("%d",&col[i]);
		col[i]--;
	}
	for (int i = 1 ; i <= m ; i++) {
		int u,v;
		scanf("%d %d",&u,&v);
		ed[u].pb(v);
		ed[v].pb(u);
	}

	for (int i = 1 ; i <= n ; i++)
		dp[i][1 << col[i]][0] = 1;

	for (int i = 1 ; i < k ; i++) {
		for (int cur = 1 ; cur <= n ; cur++) {
			for (auto nxt : ed[cur]) {
				for (int mask = 0 ; mask < (1 << k) ; mask++) {
					if ((mask & (1 << col[cur])) == 0)
						dp[cur][mask + (1 << col[cur])][i] += dp[nxt][mask][i - 1];
				}
			}
		}
	}

	for (int i = 1 ; i < k ; i++)
		for (int cur = 1 ; cur <= n ; cur++)
			for (int mask = 0 ; mask < (1 << k) ; mask++)
				ans += dp[cur][mask][i];
	printf("%lld\n",ans);
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:38: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:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&col[i]);
   ~~~~~^~~~~~~~~~~~~~
paths.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~

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