Submission #1116829

#TimeUsernameProblemLanguageResultExecution timeMemory
11168290pt1mus23Paths (BOI18_paths)C++14
23 / 100
175 ms27568 KiB
// #pragma GCC optimize("Ofast,unroll-loops") // el psy congroo #include <bits/stdc++.h> using namespace std; #define int long long int #define ins insert #define pii pair<int,int> #define pb push_back #define endl '\n' #define putr(x) cout<<x<<endl;return; #define all(x) x.begin(),x.end() const int mod = 1e9 +7, sze = 3e5+23, inf = INT_MAX, LG = 19,pr = 31; vector<int> graph[sze]; int used[sze]; int var[6][6][6][6][6]; vector<int> ord; int col[sze]; int dp[sze]; int nxt[sze]; void dfs(int node,int idx){ if(used[node]){ return; } used[node]=1; if(idx== (ord.size()-1 )){ dp[node]=1; return; } for(auto v:graph[node]){ if(col[v]==ord[idx+1]){ dfs(v,idx+1); dp[node]+=dp[v]; } } } vector<int> co[10]; void fast(){ int n,m,k; cin>>n>>m>>k; for(int i =1;i<=n;i++){ cin>>col[i]; co[col[i]].pb(i); } int u,v; for(int i =0;i<m;i++){ cin>>u>>v; graph[u].pb(v); graph[v].pb(u); } int ans=0; vector<int> ad; for(int i =0;i<k;i++){ ad.pb(i+1); } int hash=0,pp; // for(auto v:ad) cout<<v<<" ";cout<<endl; do{ ord.clear(); vector<int> cc(5,0); ord.pb(ad[0]); cc[0]=ord[0]; for(int i =1;i<k;i++){ ord.pb(ad[i]); cc[i]=ord[i]; if( !var[cc[0]][cc[1]][cc[2]][cc[3]][cc[4]] ){ // for(auto v:ord) cout<<v<<" ,";cout<<endl; for(int j=1;j<=n;j++){ dp[j]=0; used[j]=0; } for(auto v:co[ord[0]]){ dfs(v,0); if(dp[v]){ // cout<<v<<" == "<<dp[v]<<endl; ans=(ans+dp[v])%mod; } } var[cc[0]][cc[1]][cc[2]][cc[3]][cc[4]]=1; } } }while(next_permutation(all(ad))); putr(ans); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt = 1; // cin>>tt; while(tt--){ fast(); } return 0; }

Compilation message (stderr)

paths.cpp: In function 'void dfs(long long int, long long int)':
paths.cpp:27:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if(idx== (ord.size()-1 )){
      |        ~~~^~~~~~~~~~~~~~~~~~
paths.cpp: In function 'void fast()':
paths.cpp:59:9: warning: unused variable 'hash' [-Wunused-variable]
   59 |     int hash=0,pp;
      |         ^~~~
paths.cpp:59:16: warning: unused variable 'pp' [-Wunused-variable]
   59 |     int hash=0,pp;
      |                ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...