oj.uz

Submission #473659

# Submission time Handle Problem Language Result Execution time Memory
473659 2021-09-15T19:44:42 Z Sarah_Mokhtar Paths (BOI18_paths) C++14
100 / 100
 911 ms 472912 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define read freopen("acpc.in","r",stdin);
#define LESSGO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll N=3e5+10,M=505,OO=1e16,mod=1e9+9;
int n,m,k,col[N];
vector<int>adj[N];
ll dp[N][1<<6][3];
ll solve(int src,int msk,int cnt){
    ll& ret=dp[src][msk][cnt];
    if(~ret) return ret;
    ret=(cnt==2);
    for(int i:adj[src]){
        if(msk&(1ll<<col[i])) continue;
        ret+=solve(i,msk|(1ll<<col[i]),cnt+(cnt==1));
    }
    return ret;

}
int main(){
    memset(dp,-1,sizeof dp);
    cin>>n>>m>>k;
    for(int i=0;i<n;++i) cin>>col[i];
    while(m--){
        int u,v; cin>>u>>v;
        --u,--v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        
    }
    ll ans=0;
    for(int i=0;i<n;++i){
        ans+=solve(i,1<<col[i],1);
    }
    cout<<ans<<'\n';

}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 458164 KB Output is correct
2 Correct 218 ms 458180 KB Output is correct
3 Correct 208 ms 458188 KB Output is correct
4 Correct 207 ms 458228 KB Output is correct
5 Correct 210 ms 458160 KB Output is correct
6 Correct 206 ms 458180 KB Output is correct
7 Correct 206 ms 458180 KB Output is correct
8 Correct 207 ms 458232 KB Output is correct
9 Correct 212 ms 458180 KB Output is correct
10 Correct 210 ms 458124 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 462276 KB Output is correct
2 Correct 380 ms 462176 KB Output is correct
3 Correct 776 ms 472292 KB Output is correct
4 Correct 463 ms 466084 KB Output is correct
5 Correct 444 ms 466004 KB Output is correct
6 Correct 644 ms 470180 KB Output is correct
7 Correct 777 ms 472244 KB Output is correct
8 Correct 797 ms 472912 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 458164 KB Output is correct
2 Correct 218 ms 458180 KB Output is correct
3 Correct 208 ms 458188 KB Output is correct
4 Correct 207 ms 458228 KB Output is correct
5 Correct 210 ms 458160 KB Output is correct
6 Correct 206 ms 458180 KB Output is correct
7 Correct 206 ms 458180 KB Output is correct
8 Correct 207 ms 458232 KB Output is correct
9 Correct 212 ms 458180 KB Output is correct
10 Correct 210 ms 458124 KB Output is correct
11 Correct 407 ms 462276 KB Output is correct
12 Correct 380 ms 462176 KB Output is correct
13 Correct 776 ms 472292 KB Output is correct
14 Correct 463 ms 466084 KB Output is correct
15 Correct 444 ms 466004 KB Output is correct
16 Correct 644 ms 470180 KB Output is correct
17 Correct 777 ms 472244 KB Output is correct
18 Correct 797 ms 472912 KB Output is correct
19 Correct 416 ms 464584 KB Output is correct
20 Correct 387 ms 463936 KB Output is correct
21 Correct 757 ms 472232 KB Output is correct
22 Correct 503 ms 466096 KB Output is correct
23 Correct 470 ms 466084 KB Output is correct
24 Correct 638 ms 470196 KB Output is correct
25 Correct 799 ms 472124 KB Output is correct
26 Correct 725 ms 472820 KB Output is correct
27 Correct 392 ms 463988 KB Output is correct
28 Correct 444 ms 465508 KB Output is correct
29 Correct 911 ms 472132 KB Output is correct
30 Correct 728 ms 468740 KB Output is correct
31 Correct 734 ms 468832 KB Output is correct
32 Correct 842 ms 472280 KB Output is correct
33 Correct 209 ms 458148 KB Output is correct
34 Correct 208 ms 458232 KB Output is correct
35 Correct 209 ms 458308 KB Output is correct
36 Correct 214 ms 458216 KB Output is correct
37 Correct 214 ms 458208 KB Output is correct
38 Correct 211 ms 458120 KB Output is correct
39 Correct 209 ms 458180 KB Output is correct
40 Correct 211 ms 458228 KB Output is correct
41 Correct 207 ms 458228 KB Output is correct
42 Correct 214 ms 458288 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 458180 KB Output is correct
2 Correct 310 ms 459892 KB Output is correct
3 Correct 266 ms 459876 KB Output is correct
4 Correct 352 ms 461960 KB Output is correct
5 Correct 336 ms 462752 KB Output is correct
6 Correct 418 ms 461976 KB Output is correct
7 Correct 273 ms 459944 KB Output is correct
8 Correct 368 ms 462036 KB Output is correct
9 Correct 345 ms 462704 KB Output is correct
10 Correct 367 ms 462756 KB Output is correct
11 Correct 435 ms 461036 KB Output is correct
12 Correct 342 ms 461884 KB Output is correct
13 Correct 398 ms 461108 KB Output is correct
14 Correct 386 ms 461928 KB Output is correct
15 Correct 380 ms 462096 KB Output is correct
16 Correct 207 ms 458236 KB Output is correct
17 Correct 206 ms 458176 KB Output is correct
18 Correct 208 ms 458340 KB Output is correct
19 Correct 210 ms 458224 KB Output is correct
20 Correct 211 ms 458180 KB Output is correct
21 Correct 216 ms 458184 KB Output is correct
22 Correct 212 ms 458304 KB Output is correct
23 Correct 211 ms 458184 KB Output is correct
24 Correct 207 ms 458216 KB Output is correct
25 Correct 210 ms 458204 KB Output is correct