Submission #416075

#TimeUsernameProblemLanguageResultExecution timeMemory
416075Pichon5Paths (BOI18_paths)C++17
70 / 100
666 ms95916 KiB
#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][32]; 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(){ 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 (stderr)

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")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...