oj.uz

Submission #416076

# Submission time Handle Problem Language Result Execution time Memory
416076 2021-06-01T22:30:27 Z Pichon5 Paths (BOI18_paths) C++17
100 / 100
 776 ms 171056 KB 
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define vi vector<int>
#define vll vector<ll>
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//"\n" __builtin_popcount
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const int tam=300005;
vll G[tam];
ll C[tam];
ll res=0;
ll dp[tam][64];
ll dfs(ll nodo, ll mask){
   if(__builtin_popcount(mask)==5)return 0;
   if(dp[nodo][mask]!=-1)return dp[nodo][mask];
   dp[nodo][mask]=0;
   for(auto it : G[nodo]){
      if(mask&(1<<C[it]))continue;
      dp[nodo][mask]+=1+dfs(it,mask|(1<<C[it]));
   }
   return dp[nodo][mask];
}
int  main(){
   fast
   ll n,m,k,x,a,b;
   memset(dp,-1,sizeof(dp));
   cin>>n>>m>>k;
   for(int i=1;i<=n;i++){
      cin>>x;
      C[i]=x-1;
   }   
   for(int i=0;i<m;i++){
      cin>>a>>b;
      G[a].pb(b);
      G[b].pb(a);
   }
   for(int i=1;i<=n;i++){
      res+=dfs(i,(1<<C[i]));
   }
   cout<<res<<endl;
   
   return 0;
}

Compilation message

paths.cpp:12: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   12 | #pragma GCC optimization ("O3")
      | 
paths.cpp:13: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   13 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 157572 KB Output is correct
2 Correct 88 ms 157616 KB Output is correct
3 Correct 81 ms 157532 KB Output is correct
4 Correct 81 ms 157588 KB Output is correct
5 Correct 108 ms 157556 KB Output is correct
6 Correct 83 ms 157564 KB Output is correct
7 Correct 101 ms 157632 KB Output is correct
8 Correct 83 ms 157576 KB Output is correct
9 Correct 98 ms 157620 KB Output is correct
10 Correct 99 ms 157628 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 164884 KB Output is correct
2 Correct 178 ms 164712 KB Output is correct
3 Correct 608 ms 170568 KB Output is correct
4 Correct 223 ms 165924 KB Output is correct
5 Correct 220 ms 165968 KB Output is correct
6 Correct 463 ms 168088 KB Output is correct
7 Correct 640 ms 170508 KB Output is correct
8 Correct 583 ms 171044 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 157572 KB Output is correct
2 Correct 88 ms 157616 KB Output is correct
3 Correct 81 ms 157532 KB Output is correct
4 Correct 81 ms 157588 KB Output is correct
5 Correct 108 ms 157556 KB Output is correct
6 Correct 83 ms 157564 KB Output is correct
7 Correct 101 ms 157632 KB Output is correct
8 Correct 83 ms 157576 KB Output is correct
9 Correct 98 ms 157620 KB Output is correct
10 Correct 99 ms 157628 KB Output is correct
11 Correct 191 ms 164884 KB Output is correct
12 Correct 178 ms 164712 KB Output is correct
13 Correct 608 ms 170568 KB Output is correct
14 Correct 223 ms 165924 KB Output is correct
15 Correct 220 ms 165968 KB Output is correct
16 Correct 463 ms 168088 KB Output is correct
17 Correct 640 ms 170508 KB Output is correct
18 Correct 583 ms 171044 KB Output is correct
19 Correct 202 ms 164892 KB Output is correct
20 Correct 181 ms 164680 KB Output is correct
21 Correct 535 ms 170512 KB Output is correct
22 Correct 272 ms 165952 KB Output is correct
23 Correct 225 ms 166024 KB Output is correct
24 Correct 360 ms 168048 KB Output is correct
25 Correct 488 ms 170512 KB Output is correct
26 Correct 438 ms 171056 KB Output is correct
27 Correct 204 ms 164764 KB Output is correct
28 Correct 234 ms 166352 KB Output is correct
29 Correct 587 ms 170416 KB Output is correct
30 Correct 488 ms 167548 KB Output is correct
31 Correct 525 ms 167736 KB Output is correct
32 Correct 776 ms 170528 KB Output is correct
33 Correct 94 ms 157596 KB Output is correct
34 Correct 86 ms 157548 KB Output is correct
35 Correct 103 ms 157548 KB Output is correct
36 Correct 106 ms 157584 KB Output is correct
37 Correct 102 ms 157552 KB Output is correct
38 Correct 89 ms 157580 KB Output is correct
39 Correct 91 ms 157552 KB Output is correct
40 Correct 96 ms 157620 KB Output is correct
41 Correct 91 ms 157540 KB Output is correct
42 Correct 87 ms 157544 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 157588 KB Output is correct
2 Correct 140 ms 159804 KB Output is correct
3 Correct 118 ms 160604 KB Output is correct
4 Correct 195 ms 163292 KB Output is correct
5 Correct 192 ms 163716 KB Output is correct
6 Correct 288 ms 163296 KB Output is correct
7 Correct 125 ms 160624 KB Output is correct
8 Correct 207 ms 163196 KB Output is correct
9 Correct 193 ms 163720 KB Output is correct
10 Correct 185 ms 163900 KB Output is correct
11 Correct 250 ms 161824 KB Output is correct
12 Correct 190 ms 162688 KB Output is correct
13 Correct 233 ms 162156 KB Output is correct
14 Correct 292 ms 163300 KB Output is correct
15 Correct 246 ms 163380 KB Output is correct
16 Correct 105 ms 157624 KB Output is correct
17 Correct 98 ms 157564 KB Output is correct
18 Correct 97 ms 157560 KB Output is correct
19 Correct 112 ms 157636 KB Output is correct
20 Correct 91 ms 157620 KB Output is correct
21 Correct 84 ms 157608 KB Output is correct
22 Correct 83 ms 157652 KB Output is correct
23 Correct 86 ms 157668 KB Output is correct
24 Correct 116 ms 157520 KB Output is correct
25 Correct 89 ms 157580 KB Output is correct