Submission #63184

#	Time	Username	Problem	Language	Result	Execution time	Memory
63184		khsoo01	Paths (BOI18_paths)	C++11	100 / 100	741 ms	55884 KiB

paths

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 300005;

ll n, m, k, a[N], dt[1<<5][N], ans;

vector<ll> adj[N];

int main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		a[i]--;
	}
	for(ll i=1;i<=m;i++) {
		ll A, B;
		scanf("%lld%lld",&A,&B);
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	for(ll x=1;x<(1<<k);x++) {
		for(ll i=1;i<=n;i++) {
			ll j = (1<<a[i]);
			if(!(j & x)) continue;
			if(j == x) dt[x][i] = 1;
			for(auto &T : adj[i]) {
				dt[x][i] += dt[x-j][T];
			}
			ans += dt[x][i];
		}
	}
	printf("%lld\n",ans-n);
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
   ~~~~~^~~~~~~~~~~~~~
paths.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&A,&B);
   ~~~~~^~~~~~~~~~~~~~~~~~

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