oj.uz

답안 #716416

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
716416 2023-03-30T05:02:37 Z Iliya Paths (BOI18_paths) C++17
23 / 100
 308 ms 66332 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ones(x) __builtin_popcount(x)
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
int n, m, k, C[N], dp[N][(1 << 5) + 10];
vector<int> Adj[N]; ll ans;
signed main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &C[i]), C[i]--;
	for (int i = 0, u, v; i < m; i++)
		scanf("%d%d", &u, &v), Adj[u].pb(v), Adj[v].pb(u);
	for (int i = 1; i <= n; i++) 
		dp[i][(1 << C[i])] = 1;
	for (int mask = 1; mask < (1 << k); mask++) if (ones(mask) != 1) 
		for (int i = 1; i <= n; i++) if (mask & (1 << C[i]))
			for (int u : Adj[i]) if ((mask & (1 << C[u])) and C[u] != C[i])
				dp[i][mask] += dp[u][mask ^ (1 << C[i])];
	for (int i = 1; i <= n; i++)
		for (int mask = 1; mask < (1 << k); mask++) 
			if (ones(mask) != 1) ans += dp[i][mask];
	printf("%I64d", ans);
	return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:24:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
   24 |  printf("%I64d", ans);
      |          ~~~~^   ~~~
      |              |   |
      |              int ll {aka long long int}
      |          %I64lld
paths.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
paths.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d", &C[i]), C[i]--;
      |   ~~~~~^~~~~~~~~~~~~
paths.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d%d", &u, &v), Adj[u].pb(v), Adj[v].pb(u);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

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

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 11728 KB Output is correct
2 Correct 69 ms 10952 KB Output is correct
3 Correct 308 ms 66332 KB Output is correct
4 Correct 97 ms 16728 KB Output is correct
5 Correct 95 ms 16796 KB Output is correct
6 Incorrect 203 ms 48232 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7252 KB Output is correct
11 Correct 88 ms 11728 KB Output is correct
12 Correct 69 ms 10952 KB Output is correct
13 Correct 308 ms 66332 KB Output is correct
14 Correct 97 ms 16728 KB Output is correct
15 Correct 95 ms 16796 KB Output is correct
16 Incorrect 203 ms 48232 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Incorrect 40 ms 8532 KB Output isn't correct
3 Halted 0 ms 0 KB -