oj.uz

답안 #117477

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -