oj.uz

Submission #416074

# Submission time Handle Problem Language Result Execution time Memory
416074 2021-06-01T22:27:22 Z Pichon5 Paths (BOI18_paths) C++17
70 / 100
 864 ms 100664 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;
vi G[tam];
ll C[tam];
ll res=0;
ll dp[tam][33];
ll dfs(int nodo, int mask){
   if(__builtin_popcount(mask)==4)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(){
   int 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 47 ms 84804 KB Output is correct
2 Correct 56 ms 84816 KB Output is correct
3 Correct 55 ms 84748 KB Output is correct
4 Correct 49 ms 84716 KB Output is correct
5 Correct 54 ms 84720 KB Output is correct
6 Correct 56 ms 84764 KB Output is correct
7 Correct 56 ms 84788 KB Output is correct
8 Correct 47 ms 84772 KB Output is correct
9 Correct 53 ms 84820 KB Output is correct
10 Correct 52 ms 84712 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 91212 KB Output is correct
2 Correct 254 ms 90672 KB Output is correct
3 Correct 696 ms 100000 KB Output is correct
4 Correct 374 ms 92832 KB Output is correct
5 Correct 323 ms 92828 KB Output is correct
6 Correct 645 ms 97592 KB Output is correct
7 Correct 772 ms 100000 KB Output is correct
8 Correct 711 ms 100556 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 84804 KB Output is correct
2 Correct 56 ms 84816 KB Output is correct
3 Correct 55 ms 84748 KB Output is correct
4 Correct 49 ms 84716 KB Output is correct
5 Correct 54 ms 84720 KB Output is correct
6 Correct 56 ms 84764 KB Output is correct
7 Correct 56 ms 84788 KB Output is correct
8 Correct 47 ms 84772 KB Output is correct
9 Correct 53 ms 84820 KB Output is correct
10 Correct 52 ms 84712 KB Output is correct
11 Correct 289 ms 91212 KB Output is correct
12 Correct 254 ms 90672 KB Output is correct
13 Correct 696 ms 100000 KB Output is correct
14 Correct 374 ms 92832 KB Output is correct
15 Correct 323 ms 92828 KB Output is correct
16 Correct 645 ms 97592 KB Output is correct
17 Correct 772 ms 100000 KB Output is correct
18 Correct 711 ms 100556 KB Output is correct
19 Correct 292 ms 91280 KB Output is correct
20 Correct 225 ms 90564 KB Output is correct
21 Correct 650 ms 100000 KB Output is correct
22 Correct 344 ms 92796 KB Output is correct
23 Correct 360 ms 92748 KB Output is correct
24 Correct 630 ms 97520 KB Output is correct
25 Correct 848 ms 100008 KB Output is correct
26 Correct 789 ms 100664 KB Output is correct
27 Correct 240 ms 90676 KB Output is correct
28 Correct 288 ms 92096 KB Output is correct
29 Correct 725 ms 99992 KB Output is correct
30 Correct 749 ms 95844 KB Output is correct
31 Correct 663 ms 95880 KB Output is correct
32 Correct 864 ms 100012 KB Output is correct
33 Correct 58 ms 84792 KB Output is correct
34 Correct 52 ms 84796 KB Output is correct
35 Correct 53 ms 84824 KB Output is correct
36 Correct 49 ms 84768 KB Output is correct
37 Correct 49 ms 84812 KB Output is correct
38 Correct 54 ms 84744 KB Output is correct
39 Correct 54 ms 84836 KB Output is correct
40 Correct 47 ms 84816 KB Output is correct
41 Correct 56 ms 84792 KB Output is correct
42 Correct 54 ms 84820 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 84812 KB Output is correct
2 Incorrect 125 ms 86596 KB Output isn't correct
3 Halted 0 ms 0 KB -