# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
952947 |
2024-03-25T06:47:24 Z |
koukirocks |
Paths (BOI18_paths) |
C++17 |
|
213 ms |
78808 KB |
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
namespace{using namespace std;}
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=3e5+10+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
int n,m,k;
int clr[MAX];
vector<int> G[MAX];
ll dp[MAX][(1<<4)+10];
int main() {
speed;
cin>>n>>m>>k;
for (int i=1;i<=n;i++) {
cin>>clr[i];
clr[i]--;
}
for (int i=0;i<m;i++) {
int a,b;
cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
memset(dp,0,sizeof(dp));
for (int i=1;i<=n;i++) {
for (int j:G[i]) {
if (clr[i]==clr[j]) continue;
dp[i][(1<<clr[j])]++;
}
}
for (int i=1;i<=n;i++) {
for (int j:G[i]) {
if (clr[i]==clr[j]) continue;
for (int c=0;c<k;c++) {
if (clr[i]==c) continue;
dp[i][(1<<c)|(1<<clr[j])]+=dp[j][(1<<c)];
}
}
}
ll ans=0;
if (k>=2) {
for (int i=1;i<=n;i++) {
for (int c=0;c<k;c++) {
if (c==clr[i]) continue;
ans+=dp[i][(1<<c)];
}
}
}
if (k>=3) {
for (int i=1;i<=n;i++) {
for (int c1=0;c1<k;c1++) {
if (c1==clr[i]) continue;
for (int c2=c1+1;c2<k;c2++) {
if (c2==clr[i]) continue;
ans+=dp[i][(1<<c1)|(1<<c2)];
}
}
}
}
if (k>=4) {
for (int i=1;i<=n;i++) {
for (int s=7;s<(1<<k);s++) {
if (__builtin_popcount(s)!=3) continue;
if (s&(1<<clr[i])) continue;
for (int c1=0;c1<k;c1++) {
if (c1==clr[i]) continue;
if (!(s&(1<<c1))) continue;
ans+=dp[i][(1<<c1)]*dp[i][s^(1<<c1)];
}
}
}
}
if (k>=5) {
for (int i=1;i<=n;i++) {
int s=(1<<k)^(1<<clr[i]);
for (int c1=0;c1<k;c1++) {
if (c1==clr[i]) continue;
for (int c2=c1+1;c2<k;c2++) {
if (c2==clr[i]) continue;
ans+=dp[i][s^(1<<c1)^(1<<c2)]*dp[i][(1<<c1)|(1<<c2)];
}
}
}
}
cout<<ans<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
68440 KB |
Output is correct |
2 |
Correct |
10 ms |
68440 KB |
Output is correct |
3 |
Correct |
10 ms |
68444 KB |
Output is correct |
4 |
Correct |
10 ms |
68572 KB |
Output is correct |
5 |
Correct |
10 ms |
68508 KB |
Output is correct |
6 |
Correct |
10 ms |
68444 KB |
Output is correct |
7 |
Correct |
10 ms |
68488 KB |
Output is correct |
8 |
Correct |
10 ms |
68444 KB |
Output is correct |
9 |
Correct |
10 ms |
68504 KB |
Output is correct |
10 |
Correct |
10 ms |
68440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
72020 KB |
Output is correct |
2 |
Correct |
46 ms |
72120 KB |
Output is correct |
3 |
Correct |
164 ms |
78088 KB |
Output is correct |
4 |
Correct |
74 ms |
73044 KB |
Output is correct |
5 |
Correct |
70 ms |
73060 KB |
Output is correct |
6 |
Correct |
127 ms |
76396 KB |
Output is correct |
7 |
Correct |
182 ms |
77948 KB |
Output is correct |
8 |
Correct |
189 ms |
78808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
68440 KB |
Output is correct |
2 |
Correct |
10 ms |
68440 KB |
Output is correct |
3 |
Correct |
10 ms |
68444 KB |
Output is correct |
4 |
Correct |
10 ms |
68572 KB |
Output is correct |
5 |
Correct |
10 ms |
68508 KB |
Output is correct |
6 |
Correct |
10 ms |
68444 KB |
Output is correct |
7 |
Correct |
10 ms |
68488 KB |
Output is correct |
8 |
Correct |
10 ms |
68444 KB |
Output is correct |
9 |
Correct |
10 ms |
68504 KB |
Output is correct |
10 |
Correct |
10 ms |
68440 KB |
Output is correct |
11 |
Correct |
62 ms |
72020 KB |
Output is correct |
12 |
Correct |
46 ms |
72120 KB |
Output is correct |
13 |
Correct |
164 ms |
78088 KB |
Output is correct |
14 |
Correct |
74 ms |
73044 KB |
Output is correct |
15 |
Correct |
70 ms |
73060 KB |
Output is correct |
16 |
Correct |
127 ms |
76396 KB |
Output is correct |
17 |
Correct |
182 ms |
77948 KB |
Output is correct |
18 |
Correct |
189 ms |
78808 KB |
Output is correct |
19 |
Correct |
56 ms |
72016 KB |
Output is correct |
20 |
Correct |
46 ms |
72076 KB |
Output is correct |
21 |
Correct |
163 ms |
77952 KB |
Output is correct |
22 |
Correct |
75 ms |
73044 KB |
Output is correct |
23 |
Correct |
66 ms |
73040 KB |
Output is correct |
24 |
Correct |
146 ms |
76224 KB |
Output is correct |
25 |
Correct |
185 ms |
77984 KB |
Output is correct |
26 |
Correct |
174 ms |
78728 KB |
Output is correct |
27 |
Correct |
49 ms |
72152 KB |
Output is correct |
28 |
Correct |
59 ms |
72784 KB |
Output is correct |
29 |
Correct |
213 ms |
78088 KB |
Output is correct |
30 |
Correct |
149 ms |
74696 KB |
Output is correct |
31 |
Correct |
132 ms |
74948 KB |
Output is correct |
32 |
Correct |
190 ms |
77904 KB |
Output is correct |
33 |
Correct |
13 ms |
68696 KB |
Output is correct |
34 |
Correct |
10 ms |
68444 KB |
Output is correct |
35 |
Correct |
10 ms |
68440 KB |
Output is correct |
36 |
Correct |
10 ms |
68444 KB |
Output is correct |
37 |
Correct |
10 ms |
68444 KB |
Output is correct |
38 |
Correct |
12 ms |
68472 KB |
Output is correct |
39 |
Correct |
10 ms |
68444 KB |
Output is correct |
40 |
Correct |
10 ms |
68772 KB |
Output is correct |
41 |
Correct |
11 ms |
68504 KB |
Output is correct |
42 |
Correct |
10 ms |
68496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
68444 KB |
Output is correct |
2 |
Incorrect |
22 ms |
69496 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |