답안 #789522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
789522	2023-07-21T13:07:06 Z	Trisanu_Das	Paths (BOI18_paths)	C++17	100 / 100	367 ms	59864 KB

paths

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int n, m, k, a[300005], dt[1 << 5][300005], ans, u, v;
vector<int> adj[300005];
 
signed main(){
  cin >> n >> m >> k;
  for(int i = 1; i < n + 1; i++) {cin >> a[i]; a[i]--;}
  for(int i = 1; i < m + 1; i++){
    cin >> u >> v;
    adj[u].push_back(v); adj[v].push_back(u);
  }
  for(int m = 1; m < (1 << k); m++){
    for(int u = 1; u < n + 1; u++){
      int j = (1 << a[u]);
      if(!(j & m)) continue;
      if(j == m) dt[m][u] = 1;
      for(auto v : adj[u]) dt[m][u] += dt[m - j][v];
      ans += dt[m][u];
    }
  }
  cout << ans - n << '\n';
}

Subtask #1

23.0 / 23.0

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

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	116 ms	14840 KB	Output is correct
2	Correct	120 ms	16780 KB	Output is correct
3	Correct	302 ms	41080 KB	Output is correct
4	Correct	149 ms	19760 KB	Output is correct
5	Correct	154 ms	19272 KB	Output is correct
6	Correct	212 ms	32756 KB	Output is correct
7	Correct	275 ms	41104 KB	Output is correct
8	Correct	289 ms	41612 KB	Output is correct

Subtask #3

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	4 ms	7380 KB	Output is correct
3	Correct	5 ms	7348 KB	Output is correct
4	Correct	3 ms	7380 KB	Output is correct
5	Correct	4 ms	7368 KB	Output is correct
6	Correct	5 ms	7380 KB	Output is correct
7	Correct	4 ms	7484 KB	Output is correct
8	Correct	4 ms	7464 KB	Output is correct
9	Correct	4 ms	7360 KB	Output is correct
10	Correct	4 ms	7380 KB	Output is correct
11	Correct	116 ms	14840 KB	Output is correct
12	Correct	120 ms	16780 KB	Output is correct
13	Correct	302 ms	41080 KB	Output is correct
14	Correct	149 ms	19760 KB	Output is correct
15	Correct	154 ms	19272 KB	Output is correct
16	Correct	212 ms	32756 KB	Output is correct
17	Correct	275 ms	41104 KB	Output is correct
18	Correct	289 ms	41612 KB	Output is correct
19	Correct	122 ms	17692 KB	Output is correct
20	Correct	115 ms	16844 KB	Output is correct
21	Correct	282 ms	41084 KB	Output is correct
22	Correct	137 ms	19724 KB	Output is correct
23	Correct	147 ms	19220 KB	Output is correct
24	Correct	215 ms	32816 KB	Output is correct
25	Correct	274 ms	41036 KB	Output is correct
26	Correct	312 ms	41668 KB	Output is correct
27	Correct	103 ms	16844 KB	Output is correct
28	Correct	144 ms	19804 KB	Output is correct
29	Correct	365 ms	59864 KB	Output is correct
30	Correct	235 ms	38888 KB	Output is correct
31	Correct	247 ms	37888 KB	Output is correct
32	Correct	367 ms	59836 KB	Output is correct
33	Correct	4 ms	7380 KB	Output is correct
34	Correct	9 ms	7508 KB	Output is correct
35	Correct	3 ms	7380 KB	Output is correct
36	Correct	3 ms	7356 KB	Output is correct
37	Correct	3 ms	7356 KB	Output is correct
38	Correct	3 ms	7380 KB	Output is correct
39	Correct	4 ms	7380 KB	Output is correct
40	Correct	3 ms	7380 KB	Output is correct
41	Correct	3 ms	7380 KB	Output is correct
42	Correct	3 ms	7380 KB	Output is correct

Subtask #4

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	7508 KB	Output is correct
2	Correct	35 ms	10600 KB	Output is correct
3	Correct	42 ms	10300 KB	Output is correct
4	Correct	83 ms	18400 KB	Output is correct
5	Correct	64 ms	18880 KB	Output is correct
6	Correct	126 ms	37356 KB	Output is correct
7	Correct	52 ms	10444 KB	Output is correct
8	Correct	94 ms	24792 KB	Output is correct
9	Correct	73 ms	25248 KB	Output is correct
10	Correct	106 ms	24212 KB	Output is correct
11	Correct	71 ms	23780 KB	Output is correct
12	Correct	78 ms	29012 KB	Output is correct
13	Correct	79 ms	22816 KB	Output is correct
14	Correct	116 ms	37372 KB	Output is correct
15	Correct	152 ms	37448 KB	Output is correct
16	Correct	4 ms	7380 KB	Output is correct
17	Correct	4 ms	7380 KB	Output is correct
18	Correct	4 ms	7352 KB	Output is correct
19	Correct	3 ms	7352 KB	Output is correct
20	Correct	3 ms	7356 KB	Output is correct
21	Correct	4 ms	7484 KB	Output is correct
22	Correct	5 ms	7380 KB	Output is correct
23	Correct	4 ms	7480 KB	Output is correct
24	Correct	4 ms	7352 KB	Output is correct
25	Correct	3 ms	7380 KB	Output is correct