답안 #1072903

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1072903 2024-08-24T06:48:27 Z fatman87878 Paths (BOI18_paths) C++17
100 / 100
325 ms 97104 KB
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=3e5+5;

int n,m,k,col[maxN];

ll dp[maxN][1<<5],ans;

vector<int> adj[maxN];

int main(){
    cin>>n>>m>>k;
    for(int i = 1;i<=n;i++)cin>>col[i],--col[i],dp[i][1<<col[i]]=1;
    for(int a,b;m--;)cin>>a>>b,adj[adj[b].emplace_back(a)].emplace_back(b);
    for(int mask = 0;mask<1<<k;mask++)for(int i = 1;i<=n;i++)if(mask>>col[i]&1)for(int j:adj[i])dp[i][mask]+=dp[j][mask^(1<<col[i])];
    for(int mask = 0;mask<1<<k;mask++)for(int i = 1;i<=n;i++)if(__builtin_popcount(mask)>1)ans+=dp[i][mask];
    cout<<ans;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7452 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7484 KB Output is correct
6 Correct 3 ms 7476 KB Output is correct
7 Correct 3 ms 7492 KB Output is correct
8 Correct 3 ms 7492 KB Output is correct
9 Correct 4 ms 7496 KB Output is correct
10 Correct 4 ms 7260 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 15216 KB Output is correct
2 Correct 93 ms 13392 KB Output is correct
3 Correct 284 ms 96532 KB Output is correct
4 Correct 132 ms 22868 KB Output is correct
5 Correct 127 ms 22868 KB Output is correct
6 Correct 218 ms 69348 KB Output is correct
7 Correct 266 ms 96596 KB Output is correct
8 Correct 258 ms 97104 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7452 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7484 KB Output is correct
6 Correct 3 ms 7476 KB Output is correct
7 Correct 3 ms 7492 KB Output is correct
8 Correct 3 ms 7492 KB Output is correct
9 Correct 4 ms 7496 KB Output is correct
10 Correct 4 ms 7260 KB Output is correct
11 Correct 106 ms 15216 KB Output is correct
12 Correct 93 ms 13392 KB Output is correct
13 Correct 284 ms 96532 KB Output is correct
14 Correct 132 ms 22868 KB Output is correct
15 Correct 127 ms 22868 KB Output is correct
16 Correct 218 ms 69348 KB Output is correct
17 Correct 266 ms 96596 KB Output is correct
18 Correct 258 ms 97104 KB Output is correct
19 Correct 116 ms 15192 KB Output is correct
20 Correct 80 ms 13512 KB Output is correct
21 Correct 265 ms 96440 KB Output is correct
22 Correct 145 ms 22864 KB Output is correct
23 Correct 134 ms 22860 KB Output is correct
24 Correct 201 ms 69316 KB Output is correct
25 Correct 274 ms 96596 KB Output is correct
26 Correct 265 ms 97104 KB Output is correct
27 Correct 83 ms 13388 KB Output is correct
28 Correct 114 ms 16728 KB Output is correct
29 Correct 325 ms 96512 KB Output is correct
30 Correct 222 ms 55496 KB Output is correct
31 Correct 222 ms 55344 KB Output is correct
32 Correct 325 ms 96424 KB Output is correct
33 Correct 4 ms 7516 KB Output is correct
34 Correct 3 ms 7516 KB Output is correct
35 Correct 3 ms 7768 KB Output is correct
36 Correct 3 ms 7260 KB Output is correct
37 Correct 3 ms 7516 KB Output is correct
38 Correct 3 ms 7512 KB Output is correct
39 Correct 4 ms 7516 KB Output is correct
40 Correct 3 ms 7516 KB Output is correct
41 Correct 3 ms 7504 KB Output is correct
42 Correct 3 ms 7256 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7260 KB Output is correct
2 Correct 32 ms 9288 KB Output is correct
3 Correct 31 ms 9296 KB Output is correct
4 Correct 76 ms 37040 KB Output is correct
5 Correct 72 ms 37572 KB Output is correct
6 Correct 154 ms 36948 KB Output is correct
7 Correct 31 ms 9296 KB Output is correct
8 Correct 111 ms 36900 KB Output is correct
9 Correct 80 ms 37576 KB Output is correct
10 Correct 116 ms 37652 KB Output is correct
11 Correct 75 ms 23000 KB Output is correct
12 Correct 84 ms 30540 KB Output is correct
13 Correct 68 ms 23376 KB Output is correct
14 Correct 115 ms 36812 KB Output is correct
15 Correct 131 ms 36948 KB Output is correct
16 Correct 3 ms 7512 KB Output is correct
17 Correct 3 ms 7516 KB Output is correct
18 Correct 4 ms 7516 KB Output is correct
19 Correct 3 ms 7516 KB Output is correct
20 Correct 4 ms 7512 KB Output is correct
21 Correct 3 ms 7516 KB Output is correct
22 Correct 3 ms 7404 KB Output is correct
23 Correct 3 ms 7516 KB Output is correct
24 Correct 3 ms 7260 KB Output is correct
25 Correct 3 ms 7260 KB Output is correct