oj.uz

Submission #69775

# Submission time Handle Problem Language Result Execution time Memory
69775 2018-08-21T13:19:09 Z MrTEK Paths (BOI18_paths) C++14
53 / 100
 716 ms 178896 KB 
#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 = 1e5 + 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

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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2928 KB Output is correct
3 Correct 5 ms 2980 KB Output is correct
4 Correct 4 ms 2980 KB Output is correct
5 Correct 5 ms 2980 KB Output is correct
6 Correct 5 ms 3012 KB Output is correct
7 Correct 5 ms 3072 KB Output is correct
8 Correct 4 ms 3072 KB Output is correct
9 Correct 4 ms 3072 KB Output is correct
10 Correct 4 ms 3072 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 17048 KB Output is correct
2 Correct 100 ms 17048 KB Output is correct
3 Incorrect 15 ms 17048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2928 KB Output is correct
3 Correct 5 ms 2980 KB Output is correct
4 Correct 4 ms 2980 KB Output is correct
5 Correct 5 ms 2980 KB Output is correct
6 Correct 5 ms 3012 KB Output is correct
7 Correct 5 ms 3072 KB Output is correct
8 Correct 4 ms 3072 KB Output is correct
9 Correct 4 ms 3072 KB Output is correct
10 Correct 4 ms 3072 KB Output is correct
11 Correct 136 ms 17048 KB Output is correct
12 Correct 100 ms 17048 KB Output is correct
13 Incorrect 15 ms 17048 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17048 KB Output is correct
2 Correct 84 ms 17048 KB Output is correct
3 Correct 35 ms 17048 KB Output is correct
4 Correct 282 ms 164916 KB Output is correct
5 Correct 237 ms 167028 KB Output is correct
6 Correct 682 ms 167736 KB Output is correct
7 Correct 47 ms 167736 KB Output is correct
8 Correct 405 ms 169704 KB Output is correct
9 Correct 341 ms 171732 KB Output is correct
10 Correct 378 ms 173044 KB Output is correct
11 Correct 445 ms 173044 KB Output is correct
12 Correct 451 ms 173044 KB Output is correct
13 Correct 385 ms 173044 KB Output is correct
14 Correct 716 ms 177452 KB Output is correct
15 Correct 665 ms 178896 KB Output is correct
16 Correct 4 ms 178896 KB Output is correct
17 Correct 5 ms 178896 KB Output is correct
18 Correct 5 ms 178896 KB Output is correct
19 Correct 5 ms 178896 KB Output is correct
20 Correct 4 ms 178896 KB Output is correct
21 Correct 5 ms 178896 KB Output is correct
22 Correct 5 ms 178896 KB Output is correct
23 Correct 5 ms 178896 KB Output is correct
24 Correct 5 ms 178896 KB Output is correct
25 Correct 5 ms 178896 KB Output is correct