oj.uz

답안 #488100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
488100 2021-11-17T17:20:43 Z MohamedAhmed04 Paths (BOI18_paths) C++14
53 / 100
 136 ms 58000 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n , m , k ;

vector< vector<int> >adj(MAX) ;

long long dp[MAX][64] ;

void dfs(int node , int mask)
{
	if(dp[node][mask])
		return ;
	dp[node][mask] = 1 ;
	for(auto &child : adj[node])
	{
		if((mask & (1 << arr[child])))
			continue ;
		dfs(child , mask | (1 << arr[child])) ;
		dp[node][mask] += dp[child][mask | (1 << arr[child])] ;
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m>>k ;
	for(int i = 1 ; i <= n ; ++i)
	{
		cin>>arr[i] ;
		arr[i]-- ;
	}
	for(int i = 0 ; i < m ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	long long ans = 0 ;
	for(int i = 1 ; i <= n ; ++i)
	{
		dfs(i , (1 << arr[i])) ;
		ans += dp[i][(1 << arr[i])] - 1 ;
	}
	return cout<<ans<<"\n" , 0 ;
}

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 1 ms 2640 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 11768 KB Output is correct
2 Correct 56 ms 8936 KB Output is correct
3 Runtime error 10 ms 6352 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 1 ms 2640 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 1 ms 2640 KB Output is correct
8 Correct 2 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 2 ms 2640 KB Output is correct
11 Correct 71 ms 11768 KB Output is correct
12 Correct 56 ms 8936 KB Output is correct
13 Runtime error 10 ms 6352 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2640 KB Output is correct
2 Correct 31 ms 4688 KB Output is correct
3 Correct 18 ms 4776 KB Output is correct
4 Correct 107 ms 57220 KB Output is correct
5 Correct 80 ms 57936 KB Output is correct
6 Correct 116 ms 57196 KB Output is correct
7 Correct 21 ms 4748 KB Output is correct
8 Correct 102 ms 57288 KB Output is correct
9 Correct 77 ms 58000 KB Output is correct
10 Correct 95 ms 57852 KB Output is correct
11 Correct 85 ms 30780 KB Output is correct
12 Correct 71 ms 44592 KB Output is correct
13 Correct 73 ms 30900 KB Output is correct
14 Correct 136 ms 57200 KB Output is correct
15 Correct 96 ms 57280 KB Output is correct
16 Correct 1 ms 2640 KB Output is correct
17 Correct 2 ms 2640 KB Output is correct
18 Correct 3 ms 2640 KB Output is correct
19 Correct 2 ms 2640 KB Output is correct
20 Correct 2 ms 2640 KB Output is correct
21 Correct 1 ms 2640 KB Output is correct
22 Correct 1 ms 2688 KB Output is correct
23 Correct 1 ms 2640 KB Output is correct
24 Correct 2 ms 2640 KB Output is correct
25 Correct 1 ms 2640 KB Output is correct