oj.uz

Submission #117477

# Submission time Handle Problem Language Result Execution time Memory
117477 2019-06-16T07:32:25 Z ckodser Paths (BOI18_paths) C++14
23 / 100
 104 ms 13868 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];
	}
	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 2944 KB Output is correct
2 Correct 4 ms 2860 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2944 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 2944 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct
9 Correct 4 ms 2944 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 104 ms 13868 KB Output is correct
2 Correct 75 ms 12296 KB Output is correct
3 Runtime error 29 ms 7168 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 2944 KB Output is correct
2 Correct 4 ms 2860 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2944 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 2944 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct
9 Correct 4 ms 2944 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 104 ms 13868 KB Output is correct
12 Correct 75 ms 12296 KB Output is correct
13 Runtime error 29 ms 7168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -