oj.uz

Submission #473385

# Submission time Handle Problem Language Result Execution time Memory
473385 2021-09-15T12:58:51 Z fadi57 Paths (BOI18_paths) C++14
100 / 100
 675 ms 104516 KB 
#include<bits/stdc++.h>
using namespace std;
const int mx=3e5+10;
typedef long long ll;
int mod=1e9+7;
const int MXm=22;
#define F first
#define S second
const int inf=1e9+10;

 ll dp[mx][(1<<5)+5];
 int c[mx];
 vector<int>adj[mx];
 int n,m,k;
  ll solve(int node,int mask){

  ll &ret=dp[node][mask];
if(ret!=-1){

    return ret;
  }
 ret=1;

   for(auto it:adj[node]){
    if(!((1<<c[it])&mask)){

        ret+=solve(it,mask|(1<<c[it]));
    }
   }
 return ret;


  }
  int main(){
    memset(dp,-1,sizeof(dp));
    cin>>n>>m>>k;

    for(int i=1;i<=n;i++){
        cin>>c[i];
        c[i]--;
    }
  ll ans=0;
      for(int i=1;i<=m;i++){
       int a,b;cin>>a>>b;
       adj[a].push_back(b);
       adj[b].push_back(a);
      }
    for(int i=1;i<=n;i++){
        ans+=solve(i,1<<c[i]);
    }
  cout<<ans-n;

      }

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94224 KB Output is correct
2 Correct 43 ms 94148 KB Output is correct
3 Correct 43 ms 94148 KB Output is correct
4 Correct 46 ms 94204 KB Output is correct
5 Correct 45 ms 94196 KB Output is correct
6 Correct 43 ms 94280 KB Output is correct
7 Correct 41 ms 94168 KB Output is correct
8 Correct 42 ms 94112 KB Output is correct
9 Correct 43 ms 94192 KB Output is correct
10 Correct 41 ms 94148 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 97812 KB Output is correct
2 Correct 211 ms 97732 KB Output is correct
3 Correct 600 ms 103752 KB Output is correct
4 Correct 292 ms 98708 KB Output is correct
5 Correct 287 ms 98736 KB Output is correct
6 Correct 435 ms 102028 KB Output is correct
7 Correct 581 ms 103752 KB Output is correct
8 Correct 563 ms 104516 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94224 KB Output is correct
2 Correct 43 ms 94148 KB Output is correct
3 Correct 43 ms 94148 KB Output is correct
4 Correct 46 ms 94204 KB Output is correct
5 Correct 45 ms 94196 KB Output is correct
6 Correct 43 ms 94280 KB Output is correct
7 Correct 41 ms 94168 KB Output is correct
8 Correct 42 ms 94112 KB Output is correct
9 Correct 43 ms 94192 KB Output is correct
10 Correct 41 ms 94148 KB Output is correct
11 Correct 258 ms 97812 KB Output is correct
12 Correct 211 ms 97732 KB Output is correct
13 Correct 600 ms 103752 KB Output is correct
14 Correct 292 ms 98708 KB Output is correct
15 Correct 287 ms 98736 KB Output is correct
16 Correct 435 ms 102028 KB Output is correct
17 Correct 581 ms 103752 KB Output is correct
18 Correct 563 ms 104516 KB Output is correct
19 Correct 238 ms 97896 KB Output is correct
20 Correct 212 ms 97692 KB Output is correct
21 Correct 553 ms 103652 KB Output is correct
22 Correct 298 ms 98892 KB Output is correct
23 Correct 284 ms 98684 KB Output is correct
24 Correct 467 ms 102116 KB Output is correct
25 Correct 598 ms 103848 KB Output is correct
26 Correct 567 ms 104480 KB Output is correct
27 Correct 228 ms 97696 KB Output is correct
28 Correct 282 ms 98552 KB Output is correct
29 Correct 675 ms 103652 KB Output is correct
30 Correct 519 ms 100668 KB Output is correct
31 Correct 529 ms 100736 KB Output is correct
32 Correct 619 ms 103764 KB Output is correct
33 Correct 41 ms 94156 KB Output is correct
34 Correct 42 ms 94160 KB Output is correct
35 Correct 42 ms 94108 KB Output is correct
36 Correct 46 ms 94136 KB Output is correct
37 Correct 44 ms 94168 KB Output is correct
38 Correct 43 ms 94228 KB Output is correct
39 Correct 42 ms 94152 KB Output is correct
40 Correct 47 ms 94136 KB Output is correct
41 Correct 48 ms 94176 KB Output is correct
42 Correct 43 ms 94152 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94156 KB Output is correct
2 Correct 110 ms 95300 KB Output is correct
3 Correct 96 ms 95316 KB Output is correct
4 Correct 186 ms 97320 KB Output is correct
5 Correct 160 ms 98144 KB Output is correct
6 Correct 240 ms 97396 KB Output is correct
7 Correct 98 ms 95260 KB Output is correct
8 Correct 187 ms 97352 KB Output is correct
9 Correct 158 ms 98060 KB Output is correct
10 Correct 186 ms 98120 KB Output is correct
11 Correct 184 ms 96248 KB Output is correct
12 Correct 165 ms 97292 KB Output is correct
13 Correct 189 ms 96372 KB Output is correct
14 Correct 225 ms 97416 KB Output is correct
15 Correct 254 ms 97468 KB Output is correct
16 Correct 45 ms 94188 KB Output is correct
17 Correct 52 ms 94164 KB Output is correct
18 Correct 47 ms 94120 KB Output is correct
19 Correct 43 ms 94144 KB Output is correct
20 Correct 49 ms 94120 KB Output is correct
21 Correct 44 ms 94152 KB Output is correct
22 Correct 45 ms 94124 KB Output is correct
23 Correct 45 ms 94156 KB Output is correct
24 Correct 45 ms 94128 KB Output is correct
25 Correct 46 ms 94148 KB Output is correct