oj.uz

답안 #476413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476413 2021-09-26T12:54:28 Z AdamGS Paths (BOI18_paths) C++14
53 / 100
 383 ms 57920 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define int long long
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
vector<int>V[LIM];
int T[LIM], dp[LIM][1<<5];
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	rep(i, n) {
		cin >> T[i]; --T[i];
		dp[i][1<<T[i]]=1;
	}
	rep(i, m) {
		int a, b;
		cin >> a >> b; --a; --b;
		V[a].pb(b);
		V[b].pb(a);
	}
	int ans=0;
	for(int i=1; i<(1<<k); ++i) {
		rep(j, n) {
			if(__builtin_popcount(i)>1) ans+=dp[j][i];
			for(auto l : V[j]) if(!(i&(1<<T[l]))) {
				dp[l][i+(1<<T[l])]+=dp[j][i];
			}
		}
	}
	cout << ans << '\n';
}

Subtask #1
23.0 / 23.0

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

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 13852 KB Output is correct
2 Correct 84 ms 12308 KB Output is correct
3 Runtime error 47 ms 57920 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 122 ms 13852 KB Output is correct
12 Correct 84 ms 12308 KB Output is correct
13 Runtime error 47 ms 57920 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 68 ms 5688 KB Output is correct
3 Correct 28 ms 5708 KB Output is correct
4 Correct 118 ms 33336 KB Output is correct
5 Correct 91 ms 33756 KB Output is correct
6 Correct 383 ms 33436 KB Output is correct
7 Correct 38 ms 5732 KB Output is correct
8 Correct 235 ms 33396 KB Output is correct
9 Correct 149 ms 33644 KB Output is correct
10 Correct 151 ms 33868 KB Output is correct
11 Correct 201 ms 19260 KB Output is correct
12 Correct 204 ms 26372 KB Output is correct
13 Correct 187 ms 19644 KB Output is correct
14 Correct 372 ms 33348 KB Output is correct
15 Correct 371 ms 33424 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 2 ms 2636 KB Output is correct
23 Correct 3 ms 2636 KB Output is correct
24 Correct 2 ms 2636 KB Output is correct
25 Correct 1 ms 2636 KB Output is correct