oj.uz

Submission #117480

# Submission time Handle Problem Language Result Execution time Memory
117480 2019-06-16T07:34:20 Z ckodser Paths (BOI18_paths) C++14
100 / 100
 895 ms 91000 KB 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=3e5+500;

ll a[maxn];
vector<ll> ger[maxn];
ll dp[32][maxn];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	ll n,m,k;
	cin>>n>>m>>k;
	for(ll i=0;i<n;i++){
		cin>>a[i];
      a[i]--;
	}
	for(ll i=0;i<m;i++){
		ll a,b;
		cin>>a>>b;
		a--;b--;
		ger[a].pb(b);
		ger[b].pb(a);
	}
	ll ans=0;
	for(ll mas=1;mas<32;mas++){
		for(ll i=0;i<n;i++){
			if((mas>>a[i])&1){
				ll nmas=(mas^(1<<a[i]));	
				if(nmas==0){
					dp[mas][i]=1;
					continue;
				}		
				for(auto r:ger[i]){
					dp[mas][i]+=dp[nmas][r];
				}
			}
			ans+=dp[mas][i];
		}
	}
	cout<<ans;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7680 KB Output is correct
2 Correct 8 ms 7680 KB Output is correct
3 Correct 8 ms 7680 KB Output is correct
4 Correct 8 ms 7680 KB Output is correct
5 Correct 7 ms 7680 KB Output is correct
6 Correct 8 ms 7680 KB Output is correct
7 Correct 8 ms 7680 KB Output is correct
8 Correct 8 ms 7680 KB Output is correct
9 Correct 7 ms 7596 KB Output is correct
10 Correct 8 ms 7680 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 15856 KB Output is correct
2 Correct 74 ms 14812 KB Output is correct
3 Correct 895 ms 86292 KB Output is correct
4 Correct 185 ms 21624 KB Output is correct
5 Correct 186 ms 19740 KB Output is correct
6 Correct 397 ms 61800 KB Output is correct
7 Correct 628 ms 86260 KB Output is correct
8 Correct 642 ms 86668 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7680 KB Output is correct
2 Correct 8 ms 7680 KB Output is correct
3 Correct 8 ms 7680 KB Output is correct
4 Correct 8 ms 7680 KB Output is correct
5 Correct 7 ms 7680 KB Output is correct
6 Correct 8 ms 7680 KB Output is correct
7 Correct 8 ms 7680 KB Output is correct
8 Correct 8 ms 7680 KB Output is correct
9 Correct 7 ms 7596 KB Output is correct
10 Correct 8 ms 7680 KB Output is correct
11 Correct 100 ms 15856 KB Output is correct
12 Correct 74 ms 14812 KB Output is correct
13 Correct 895 ms 86292 KB Output is correct
14 Correct 185 ms 21624 KB Output is correct
15 Correct 186 ms 19740 KB Output is correct
16 Correct 397 ms 61800 KB Output is correct
17 Correct 628 ms 86260 KB Output is correct
18 Correct 642 ms 86668 KB Output is correct
19 Correct 96 ms 15924 KB Output is correct
20 Correct 73 ms 14940 KB Output is correct
21 Correct 644 ms 86264 KB Output is correct
22 Correct 221 ms 21640 KB Output is correct
23 Correct 227 ms 19668 KB Output is correct
24 Correct 421 ms 61896 KB Output is correct
25 Correct 633 ms 86196 KB Output is correct
26 Correct 633 ms 86772 KB Output is correct
27 Correct 71 ms 14840 KB Output is correct
28 Correct 118 ms 18172 KB Output is correct
29 Correct 678 ms 91000 KB Output is correct
30 Correct 430 ms 52828 KB Output is correct
31 Correct 427 ms 50488 KB Output is correct
32 Correct 719 ms 90996 KB Output is correct
33 Correct 11 ms 7680 KB Output is correct
34 Correct 8 ms 7680 KB Output is correct
35 Correct 8 ms 7680 KB Output is correct
36 Correct 8 ms 7680 KB Output is correct
37 Correct 8 ms 7552 KB Output is correct
38 Correct 8 ms 7732 KB Output is correct
39 Correct 8 ms 7680 KB Output is correct
40 Correct 8 ms 7680 KB Output is correct
41 Correct 8 ms 7680 KB Output is correct
42 Correct 7 ms 7680 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7552 KB Output is correct
2 Correct 29 ms 9848 KB Output is correct
3 Correct 28 ms 9848 KB Output is correct
4 Correct 135 ms 33884 KB Output is correct
5 Correct 101 ms 34284 KB Output is correct
6 Correct 172 ms 36168 KB Output is correct
7 Correct 29 ms 9892 KB Output is correct
8 Correct 165 ms 35340 KB Output is correct
9 Correct 128 ms 35820 KB Output is correct
10 Correct 129 ms 33960 KB Output is correct
11 Correct 86 ms 22860 KB Output is correct
12 Correct 97 ms 27876 KB Output is correct
13 Correct 80 ms 21736 KB Output is correct
14 Correct 172 ms 36216 KB Output is correct
15 Correct 169 ms 36236 KB Output is correct
16 Correct 8 ms 7680 KB Output is correct
17 Correct 7 ms 7680 KB Output is correct
18 Correct 7 ms 7808 KB Output is correct
19 Correct 8 ms 7652 KB Output is correct
20 Correct 7 ms 7680 KB Output is correct
21 Correct 8 ms 7680 KB Output is correct
22 Correct 8 ms 7680 KB Output is correct
23 Correct 8 ms 7752 KB Output is correct
24 Correct 7 ms 7680 KB Output is correct
25 Correct 7 ms 7680 KB Output is correct