oj.uz

Submission #117478

# Submission time Handle Problem Language Result Execution time Memory
117478 2019-06-16T07:33:16 Z ckodser Paths (BOI18_paths) C++14
53 / 100
 199 ms 32860 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=1e5+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 4 ms 2816 KB Output is correct
2 Correct 3 ms 2944 KB Output is correct
3 Correct 4 ms 2944 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 4 ms 2944 KB Output is correct
7 Correct 4 ms 3020 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct
9 Correct 4 ms 2816 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 11128 KB Output is correct
2 Correct 71 ms 10152 KB Output is correct
3 Runtime error 15 ms 6784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 3 ms 2944 KB Output is correct
3 Correct 4 ms 2944 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 4 ms 2944 KB Output is correct
7 Correct 4 ms 3020 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct
9 Correct 4 ms 2816 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 99 ms 11128 KB Output is correct
12 Correct 71 ms 10152 KB Output is correct
13 Runtime error 15 ms 6784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 25 ms 5924 KB Output is correct
3 Correct 25 ms 5880 KB Output is correct
4 Correct 140 ms 30428 KB Output is correct
5 Correct 105 ms 30824 KB Output is correct
6 Correct 170 ms 32760 KB Output is correct
7 Correct 25 ms 5880 KB Output is correct
8 Correct 180 ms 31992 KB Output is correct
9 Correct 118 ms 32360 KB Output is correct
10 Correct 123 ms 30540 KB Output is correct
11 Correct 93 ms 19184 KB Output is correct
12 Correct 88 ms 24412 KB Output is correct
13 Correct 97 ms 18152 KB Output is correct
14 Correct 199 ms 32788 KB Output is correct
15 Correct 181 ms 32860 KB Output is correct
16 Correct 4 ms 2944 KB Output is correct
17 Correct 4 ms 2944 KB Output is correct
18 Correct 4 ms 2816 KB Output is correct
19 Correct 5 ms 2944 KB Output is correct
20 Correct 4 ms 2816 KB Output is correct
21 Correct 4 ms 2944 KB Output is correct
22 Correct 15 ms 2944 KB Output is correct
23 Correct 4 ms 2944 KB Output is correct
24 Correct 4 ms 2816 KB Output is correct
25 Correct 4 ms 2816 KB Output is correct