oj.uz

Submission #208458

# Submission time Handle Problem Language Result Execution time Memory
208458 2020-03-11T08:58:10 Z tleontest1 Paths (BOI18_paths) C++14
100 / 100
 623 ms 118144 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define int long long
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 300005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,dp[li][(1<<5)+3];
int cev;
string s;
map<vector<int>,int> mpp[li];
vector<int> v[li],vec;

inline int dfs(int node,int ata,int mask){
	int cevv=0;
	if(mask==(1<<5)-1)return 1;
	if(~dp[node][mask])return dp[node][mask];
	if(mask!=(1<<0) && mask!=(1<<1) && mask!=(1<<2) && mask!=(1<<3) && mask!=(1<<4) && mask)cevv+=dfs(node,ata,(1<<5)-1);
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		
		//~ if(go==ata)continue;
		//~ cevv+=dfs(go,node,mask);
		if((mask&(1<<(a[go]-1)))==0)cevv+=dfs(go,node,(mask|(1<<(a[go]-1))));
	}
	return dp[node][mask]=cevv;
}

main(void){
	
	scanf("%lld %lld %lld",&n,&m,&k);
	FOR scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%lld %lld",&x,&y);
		v[x].pb(y);
		v[y].pb(x);
	}
	memset(dp,-1,sizeof(dp));
	FOR{
		
		cev+=dfs(i,0,(1<<(a[i]-1)));
	}
	printf("%lld\n",cev);
	return 0;
}

Compilation message

paths.cpp:51:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^
paths.cpp: In function 'int main()':
paths.cpp:53: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:54:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  FOR scanf("%lld",&a[i]);
      ~~~~~^~~~~~~~~~~~~~
paths.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 103672 KB Output is correct
2 Correct 63 ms 103676 KB Output is correct
3 Correct 67 ms 103672 KB Output is correct
4 Correct 64 ms 103672 KB Output is correct
5 Correct 63 ms 103672 KB Output is correct
6 Correct 63 ms 103672 KB Output is correct
7 Correct 62 ms 103672 KB Output is correct
8 Correct 63 ms 103672 KB Output is correct
9 Correct 63 ms 103672 KB Output is correct
10 Correct 63 ms 103672 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 111608 KB Output is correct
2 Correct 169 ms 111352 KB Output is correct
3 Correct 531 ms 117752 KB Output is correct
4 Correct 216 ms 112760 KB Output is correct
5 Correct 226 ms 112992 KB Output is correct
6 Correct 355 ms 115148 KB Output is correct
7 Correct 506 ms 117592 KB Output is correct
8 Correct 459 ms 118112 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 103672 KB Output is correct
2 Correct 63 ms 103676 KB Output is correct
3 Correct 67 ms 103672 KB Output is correct
4 Correct 64 ms 103672 KB Output is correct
5 Correct 63 ms 103672 KB Output is correct
6 Correct 63 ms 103672 KB Output is correct
7 Correct 62 ms 103672 KB Output is correct
8 Correct 63 ms 103672 KB Output is correct
9 Correct 63 ms 103672 KB Output is correct
10 Correct 63 ms 103672 KB Output is correct
11 Correct 168 ms 111608 KB Output is correct
12 Correct 169 ms 111352 KB Output is correct
13 Correct 531 ms 117752 KB Output is correct
14 Correct 216 ms 112760 KB Output is correct
15 Correct 226 ms 112992 KB Output is correct
16 Correct 355 ms 115148 KB Output is correct
17 Correct 506 ms 117592 KB Output is correct
18 Correct 459 ms 118112 KB Output is correct
19 Correct 178 ms 111952 KB Output is correct
20 Correct 157 ms 111608 KB Output is correct
21 Correct 481 ms 117728 KB Output is correct
22 Correct 230 ms 113016 KB Output is correct
23 Correct 207 ms 113040 KB Output is correct
24 Correct 369 ms 115156 KB Output is correct
25 Correct 488 ms 117600 KB Output is correct
26 Correct 468 ms 118144 KB Output is correct
27 Correct 187 ms 111680 KB Output is correct
28 Correct 231 ms 113272 KB Output is correct
29 Correct 613 ms 117600 KB Output is correct
30 Correct 467 ms 114576 KB Output is correct
31 Correct 505 ms 114772 KB Output is correct
32 Correct 623 ms 117496 KB Output is correct
33 Correct 63 ms 103672 KB Output is correct
34 Correct 63 ms 103672 KB Output is correct
35 Correct 64 ms 103612 KB Output is correct
36 Correct 64 ms 103620 KB Output is correct
37 Correct 61 ms 103640 KB Output is correct
38 Correct 70 ms 103672 KB Output is correct
39 Correct 60 ms 103672 KB Output is correct
40 Correct 61 ms 103672 KB Output is correct
41 Correct 65 ms 103672 KB Output is correct
42 Correct 68 ms 103672 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 103672 KB Output is correct
2 Correct 116 ms 106488 KB Output is correct
3 Correct 91 ms 106488 KB Output is correct
4 Correct 174 ms 109048 KB Output is correct
5 Correct 130 ms 109420 KB Output is correct
6 Correct 203 ms 108920 KB Output is correct
7 Correct 96 ms 106492 KB Output is correct
8 Correct 183 ms 108920 KB Output is correct
9 Correct 143 ms 109420 KB Output is correct
10 Correct 158 ms 109160 KB Output is correct
11 Correct 168 ms 107684 KB Output is correct
12 Correct 153 ms 108392 KB Output is correct
13 Correct 151 ms 107756 KB Output is correct
14 Correct 206 ms 108920 KB Output is correct
15 Correct 198 ms 109048 KB Output is correct
16 Correct 62 ms 103672 KB Output is correct
17 Correct 63 ms 103672 KB Output is correct
18 Correct 66 ms 103672 KB Output is correct
19 Correct 64 ms 103672 KB Output is correct
20 Correct 61 ms 103672 KB Output is correct
21 Correct 61 ms 103684 KB Output is correct
22 Correct 67 ms 103672 KB Output is correct
23 Correct 64 ms 103672 KB Output is correct
24 Correct 64 ms 103672 KB Output is correct
25 Correct 63 ms 103672 KB Output is correct