Submission #210839

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
210839	2020-03-18T19:24:43 Z	bash	Paths (BOI18_paths)	C++17	100 / 100	850 ms	315836 KB

paths

/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
 
#define F first
#define S second
#define endl '\n'
#define deb(x) cout<<#x<<' '<<x<<endl;
#define pb push_back
 using namespace __gnu_pbds;
using namespace std;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
/*
#ifdef IZI_KATKA
#define int __int64_t
#else
#define int __int64
#endif
*/
const long long MOD = 1e9 + 7;
const long long MAXN = 1e6 + 1;

typedef long long ll;

#define pii pair<int,int>
 
long long readInt() {
    bool minus1 = false;
    long long result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus1 = true; else result = ch-'0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus1)
        return -result;
    else
        return result;
}                
#define int ll
int a[MAXN];
int dp[MAXN][(1 << 5) + 3];
int n, m, k;                
vector<int> g[MAXN];

int solve(int v, int mask) {
	if (__builtin_popcount(mask) == k) {
		return 1;		
	}
	if (~dp[v][mask]) return dp[v][mask];
	int &ans  = dp[v][mask];
	ans = 0;
	if (__builtin_popcount(mask) > 1) {
		ans += solve(v, (1 << k) - 1);
	}
	for (int i : g[v]) {
		if ((mask >> a[i]) & 1) continue;
		ans += solve(i, mask | (1 << a[i]));
	}                                       
	return ans;
}

main() {
	#ifdef IZI_KATKA
	assert(freopen("input", "r", stdin));
    assert(freopen("output", "w", stdout));
    #endif
    n = readInt(), m = readInt(), k = readInt();
    if (k == 1) {
    	cout << 0;
    	return 0;
    }
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= n; i++) {
    	a[i] = readInt() - 1;
    }
    for (int i = 1; i <= m; i++) {
		int u = readInt(), v = readInt();
		g[v].pb(u);
		g[u].pb(v);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
    	ans += solve(i, (1 << (a[i])));
    }
    cout << ans << endl;
	return 0;
}

Compilation message

paths.cpp:101:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	201 ms	297720 KB	Output is correct
2	Correct	197 ms	297804 KB	Output is correct
3	Correct	211 ms	297720 KB	Output is correct
4	Correct	203 ms	297792 KB	Output is correct
5	Correct	24 ms	23804 KB	Output is correct
6	Correct	206 ms	297944 KB	Output is correct
7	Correct	208 ms	297912 KB	Output is correct
8	Correct	197 ms	297748 KB	Output is correct
9	Correct	218 ms	297848 KB	Output is correct
10	Correct	193 ms	297804 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	305 ms	304952 KB	Output is correct
2	Correct	275 ms	304760 KB	Output is correct
3	Correct	685 ms	310664 KB	Output is correct
4	Correct	325 ms	306196 KB	Output is correct
5	Correct	25 ms	23956 KB	Output is correct
6	Correct	523 ms	312392 KB	Output is correct
7	Correct	714 ms	315228 KB	Output is correct
8	Correct	701 ms	315784 KB	Output is correct

Subtask #3

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	201 ms	297720 KB	Output is correct
2	Correct	197 ms	297804 KB	Output is correct
3	Correct	211 ms	297720 KB	Output is correct
4	Correct	203 ms	297792 KB	Output is correct
5	Correct	24 ms	23804 KB	Output is correct
6	Correct	206 ms	297944 KB	Output is correct
7	Correct	208 ms	297912 KB	Output is correct
8	Correct	197 ms	297748 KB	Output is correct
9	Correct	218 ms	297848 KB	Output is correct
10	Correct	193 ms	297804 KB	Output is correct
11	Correct	305 ms	304952 KB	Output is correct
12	Correct	275 ms	304760 KB	Output is correct
13	Correct	685 ms	310664 KB	Output is correct
14	Correct	325 ms	306196 KB	Output is correct
15	Correct	25 ms	23956 KB	Output is correct
16	Correct	523 ms	312392 KB	Output is correct
17	Correct	714 ms	315228 KB	Output is correct
18	Correct	701 ms	315784 KB	Output is correct
19	Correct	302 ms	307836 KB	Output is correct
20	Correct	279 ms	307132 KB	Output is correct
21	Correct	713 ms	315204 KB	Output is correct
22	Correct	368 ms	309596 KB	Output is correct
23	Correct	24 ms	23800 KB	Output is correct
24	Correct	603 ms	312576 KB	Output is correct
25	Correct	850 ms	315296 KB	Output is correct
26	Correct	730 ms	315836 KB	Output is correct
27	Correct	316 ms	307008 KB	Output is correct
28	Correct	346 ms	309328 KB	Output is correct
29	Correct	850 ms	315284 KB	Output is correct
30	Correct	686 ms	311916 KB	Output is correct
31	Correct	742 ms	311932 KB	Output is correct
32	Correct	848 ms	315284 KB	Output is correct
33	Correct	203 ms	297688 KB	Output is correct
34	Correct	233 ms	297812 KB	Output is correct
35	Correct	224 ms	297720 KB	Output is correct
36	Correct	219 ms	297824 KB	Output is correct
37	Correct	27 ms	23928 KB	Output is correct
38	Correct	222 ms	297820 KB	Output is correct
39	Correct	231 ms	297744 KB	Output is correct
40	Correct	201 ms	297844 KB	Output is correct
41	Correct	211 ms	297812 KB	Output is correct
42	Correct	248 ms	297820 KB	Output is correct

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	218 ms	297804 KB	Output is correct
2	Correct	271 ms	299896 KB	Output is correct
3	Correct	234 ms	299844 KB	Output is correct
4	Correct	335 ms	302224 KB	Output is correct
5	Correct	297 ms	302520 KB	Output is correct
6	Correct	476 ms	302120 KB	Output is correct
7	Correct	241 ms	299980 KB	Output is correct
8	Correct	426 ms	302212 KB	Output is correct
9	Correct	330 ms	302520 KB	Output is correct
10	Correct	372 ms	302716 KB	Output is correct
11	Correct	374 ms	300804 KB	Output is correct
12	Correct	348 ms	301608 KB	Output is correct
13	Correct	352 ms	301076 KB	Output is correct
14	Correct	435 ms	302216 KB	Output is correct
15	Correct	411 ms	302208 KB	Output is correct
16	Correct	234 ms	297720 KB	Output is correct
17	Correct	224 ms	297848 KB	Output is correct
18	Correct	197 ms	297824 KB	Output is correct
19	Correct	196 ms	297848 KB	Output is correct
20	Correct	25 ms	23928 KB	Output is correct
21	Correct	201 ms	297848 KB	Output is correct
22	Correct	196 ms	297848 KB	Output is correct
23	Correct	199 ms	297876 KB	Output is correct
24	Correct	197 ms	297992 KB	Output is correct
25	Correct	210 ms	297824 KB	Output is correct