답안 #63177 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63177	2018-08-01T04:03:38 Z	koosaga(#1829)	Paths (BOI18_paths)	C++11	100 / 100	841 ms	52588 KB

paths

#include<bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 300005;
const int mod = 1e9 + 7;

int n, m, k, a[MAXN];
vector<int> gph[MAXN];
lint dp[32][MAXN];

int main(){
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		a[i]--;
		dp[1 << a[i]][i] = 1;
	}
	for(int i=0; i<m; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	lint ret = 0;
	for(int i=2; i<(1<<k); i++){
		if(i == (i & -i)) continue;
		for(int j=1; j<=n; j++){
			if((i >> a[j]) & 1){
				for(auto &k : gph[j]){
					dp[i][j] += dp[i ^ (1 << a[j])][k];
				}
			}
			ret += dp[i][j];
		}
	}
	cout << ret << endl;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
paths.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
paths.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s,&e);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	7416 KB	Output is correct
2	Correct	11 ms	7524 KB	Output is correct
3	Correct	12 ms	7560 KB	Output is correct
4	Correct	11 ms	7636 KB	Output is correct
5	Correct	11 ms	7636 KB	Output is correct
6	Correct	12 ms	7716 KB	Output is correct
7	Correct	11 ms	7716 KB	Output is correct
8	Correct	2 ms	7716 KB	Output is correct
9	Correct	10 ms	7716 KB	Output is correct
10	Correct	10 ms	7716 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	190 ms	11680 KB	Output is correct
2	Correct	126 ms	11680 KB	Output is correct
3	Correct	580 ms	33684 KB	Output is correct
4	Correct	296 ms	33684 KB	Output is correct
5	Correct	292 ms	33684 KB	Output is correct
6	Correct	426 ms	33684 KB	Output is correct
7	Correct	509 ms	33684 KB	Output is correct
8	Correct	726 ms	34260 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	7416 KB	Output is correct
2	Correct	11 ms	7524 KB	Output is correct
3	Correct	12 ms	7560 KB	Output is correct
4	Correct	11 ms	7636 KB	Output is correct
5	Correct	11 ms	7636 KB	Output is correct
6	Correct	12 ms	7716 KB	Output is correct
7	Correct	11 ms	7716 KB	Output is correct
8	Correct	2 ms	7716 KB	Output is correct
9	Correct	10 ms	7716 KB	Output is correct
10	Correct	10 ms	7716 KB	Output is correct
11	Correct	190 ms	11680 KB	Output is correct
12	Correct	126 ms	11680 KB	Output is correct
13	Correct	580 ms	33684 KB	Output is correct
14	Correct	296 ms	33684 KB	Output is correct
15	Correct	292 ms	33684 KB	Output is correct
16	Correct	426 ms	33684 KB	Output is correct
17	Correct	509 ms	33684 KB	Output is correct
18	Correct	726 ms	34260 KB	Output is correct
19	Correct	187 ms	34260 KB	Output is correct
20	Correct	119 ms	34260 KB	Output is correct
21	Correct	554 ms	34260 KB	Output is correct
22	Correct	276 ms	34260 KB	Output is correct
23	Correct	273 ms	34260 KB	Output is correct
24	Correct	399 ms	34260 KB	Output is correct
25	Correct	515 ms	34260 KB	Output is correct
26	Correct	551 ms	34412 KB	Output is correct
27	Correct	134 ms	34412 KB	Output is correct
28	Correct	244 ms	34412 KB	Output is correct
29	Correct	841 ms	52588 KB	Output is correct
30	Correct	518 ms	52588 KB	Output is correct
31	Correct	605 ms	52588 KB	Output is correct
32	Correct	753 ms	52588 KB	Output is correct
33	Correct	11 ms	52588 KB	Output is correct
34	Correct	12 ms	52588 KB	Output is correct
35	Correct	11 ms	52588 KB	Output is correct
36	Correct	13 ms	52588 KB	Output is correct
37	Correct	12 ms	52588 KB	Output is correct
38	Correct	11 ms	52588 KB	Output is correct
39	Correct	13 ms	52588 KB	Output is correct
40	Correct	12 ms	52588 KB	Output is correct
41	Correct	10 ms	52588 KB	Output is correct
42	Correct	10 ms	52588 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	52588 KB	Output is correct
2	Correct	49 ms	52588 KB	Output is correct
3	Correct	41 ms	52588 KB	Output is correct
4	Correct	179 ms	52588 KB	Output is correct
5	Correct	113 ms	52588 KB	Output is correct
6	Correct	374 ms	52588 KB	Output is correct
7	Correct	48 ms	52588 KB	Output is correct
8	Correct	219 ms	52588 KB	Output is correct
9	Correct	154 ms	52588 KB	Output is correct
10	Correct	176 ms	52588 KB	Output is correct
11	Correct	198 ms	52588 KB	Output is correct
12	Correct	185 ms	52588 KB	Output is correct
13	Correct	167 ms	52588 KB	Output is correct
14	Correct	333 ms	52588 KB	Output is correct
15	Correct	300 ms	52588 KB	Output is correct
16	Correct	10 ms	52588 KB	Output is correct
17	Correct	12 ms	52588 KB	Output is correct
18	Correct	11 ms	52588 KB	Output is correct
19	Correct	11 ms	52588 KB	Output is correct
20	Correct	11 ms	52588 KB	Output is correct
21	Correct	12 ms	52588 KB	Output is correct
22	Correct	11 ms	52588 KB	Output is correct
23	Correct	12 ms	52588 KB	Output is correct
24	Correct	11 ms	52588 KB	Output is correct
25	Correct	11 ms	52588 KB	Output is correct

답안 #63177

Compilation message

Subtask #1 23.0 / 23.0

Subtask #2 20.0 / 20.0

Subtask #3 27.0 / 27.0

Subtask #4 30.0 / 30.0

Subtask #1
23.0 / 23.0

Subtask #2
20.0 / 20.0

Subtask #3
27.0 / 27.0

Subtask #4
30.0 / 30.0