oj.uz

Submission #208438

# Submission time Handle Problem Language Result Execution time Memory
208438 2020-03-11T08:06:07 Z Fasho Paths (BOI18_paths) C++14
100 / 100
 589 ms 93944 KB 
#include <bits/stdc++.h>
#define N 300005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
using namespace std;

ll n,m,ar[N],sum,t,dp[N][32],pw[N],k;

vector<int> v[N];

ll f(int ind,int mask)
{
	// cout<<ind<<sp<<mask<<endl;
	if(dp[ind][mask]!=-1)
		return dp[ind][mask];
	if((pw[ar[ind]-1] & mask))
		return dp[ind][mask]=0;
	ll x=mask;
	mask=(mask|pw[ar[ind]-1]);
	ll top=1;
	for(int i=0;i<v[ind].size();i++)
	{
		// if(ind==2)
		// 	cout<<"[d]"<<sp<<v[ind][i]<<sp<<mask<<sp<<f(v[ind][i],mask)<<endl;
		top+=f(v[ind][i],mask);
	}
	return dp[ind][x]=top;
}

int main()
{
	fast;
	cin>>n>>m>>k;

	// cout<<endl;

	pw[0]=1;
	fo(i,1,5)
	pw[i]=pw[i-1]*2;
	memset(dp,-1,sizeof(dp));
	fo(i,1,6)
		pw[i]=pw[i-1]*2;
	fs(ar,n);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	fo(i,1,n)
	{
		ll x=f(i,0);
		sum+=x;
		// cout<<endl;
		// cout<<x<<endl;
	}
	// cout<<dp[1][4]<<endl;
	// sum=f(2,0);
	// cout<<sum<<endl;
	// cout<<endl;
	sum-=n;
	cout<<sum;

}

Compilation message

paths.cpp: In function 'long long int f(int, int)':
paths.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[ind].size();i++)
              ~^~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 82552 KB Output is correct
2 Correct 49 ms 82552 KB Output is correct
3 Correct 53 ms 82552 KB Output is correct
4 Correct 51 ms 82552 KB Output is correct
5 Correct 48 ms 82552 KB Output is correct
6 Correct 48 ms 82552 KB Output is correct
7 Correct 49 ms 82552 KB Output is correct
8 Correct 50 ms 82552 KB Output is correct
9 Correct 48 ms 82552 KB Output is correct
10 Correct 48 ms 82552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 86392 KB Output is correct
2 Correct 115 ms 86008 KB Output is correct
3 Correct 524 ms 93308 KB Output is correct
4 Correct 165 ms 87416 KB Output is correct
5 Correct 154 ms 87160 KB Output is correct
6 Correct 334 ms 91372 KB Output is correct
7 Correct 473 ms 93304 KB Output is correct
8 Correct 425 ms 93944 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 82552 KB Output is correct
2 Correct 49 ms 82552 KB Output is correct
3 Correct 53 ms 82552 KB Output is correct
4 Correct 51 ms 82552 KB Output is correct
5 Correct 48 ms 82552 KB Output is correct
6 Correct 48 ms 82552 KB Output is correct
7 Correct 49 ms 82552 KB Output is correct
8 Correct 50 ms 82552 KB Output is correct
9 Correct 48 ms 82552 KB Output is correct
10 Correct 48 ms 82552 KB Output is correct
11 Correct 133 ms 86392 KB Output is correct
12 Correct 115 ms 86008 KB Output is correct
13 Correct 524 ms 93308 KB Output is correct
14 Correct 165 ms 87416 KB Output is correct
15 Correct 154 ms 87160 KB Output is correct
16 Correct 334 ms 91372 KB Output is correct
17 Correct 473 ms 93304 KB Output is correct
18 Correct 425 ms 93944 KB Output is correct
19 Correct 129 ms 86264 KB Output is correct
20 Correct 110 ms 86008 KB Output is correct
21 Correct 484 ms 93332 KB Output is correct
22 Correct 166 ms 87160 KB Output is correct
23 Correct 167 ms 87392 KB Output is correct
24 Correct 347 ms 91240 KB Output is correct
25 Correct 492 ms 93304 KB Output is correct
26 Correct 445 ms 93944 KB Output is correct
27 Correct 131 ms 86008 KB Output is correct
28 Correct 144 ms 87032 KB Output is correct
29 Correct 589 ms 93268 KB Output is correct
30 Correct 440 ms 89584 KB Output is correct
31 Correct 476 ms 89584 KB Output is correct
32 Correct 589 ms 93304 KB Output is correct
33 Correct 50 ms 82552 KB Output is correct
34 Correct 48 ms 82552 KB Output is correct
35 Correct 49 ms 82552 KB Output is correct
36 Correct 53 ms 82552 KB Output is correct
37 Correct 48 ms 82552 KB Output is correct
38 Correct 48 ms 82552 KB Output is correct
39 Correct 49 ms 82552 KB Output is correct
40 Correct 48 ms 82552 KB Output is correct
41 Correct 50 ms 82552 KB Output is correct
42 Correct 48 ms 82552 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 82552 KB Output is correct
2 Correct 81 ms 83704 KB Output is correct
3 Correct 69 ms 83576 KB Output is correct
4 Correct 157 ms 86064 KB Output is correct
5 Correct 109 ms 86900 KB Output is correct
6 Correct 218 ms 86136 KB Output is correct
7 Correct 72 ms 83576 KB Output is correct
8 Correct 180 ms 86136 KB Output is correct
9 Correct 121 ms 86900 KB Output is correct
10 Correct 145 ms 86896 KB Output is correct
11 Correct 187 ms 84724 KB Output is correct
12 Correct 126 ms 85872 KB Output is correct
13 Correct 178 ms 84984 KB Output is correct
14 Correct 220 ms 86136 KB Output is correct
15 Correct 170 ms 86264 KB Output is correct
16 Correct 52 ms 82552 KB Output is correct
17 Correct 49 ms 82552 KB Output is correct
18 Correct 49 ms 82552 KB Output is correct
19 Correct 48 ms 82552 KB Output is correct
20 Correct 54 ms 82552 KB Output is correct
21 Correct 49 ms 82552 KB Output is correct
22 Correct 50 ms 82552 KB Output is correct
23 Correct 49 ms 82552 KB Output is correct
24 Correct 50 ms 82552 KB Output is correct
25 Correct 48 ms 82552 KB Output is correct