Submission #1116826

#TimeUsernameProblemLanguageResultExecution timeMemory
11168260pt1mus23Paths (BOI18_paths)C++14
23 / 100
3080 ms25096 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]; map<int,int> var; vector<int> ord; int col[sze]; int dp[sze]; int nxt[sze]; void dfs(int node,int idx){ if(idx== (ord.size()-1 ) ){ dp[node]=1; return; } for(auto v:graph[node]){ if(col[v]==ord[idx+1]){ dp[v]=0; dfs(v,idx+1); dp[node]+=dp[v]; } } } vector<int> cc[10]; void fast(){ int n,m,k; cin>>n>>m>>k; for(int i =1;i<=n;i++){ cin>>col[i]; cc[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{ hash=ad[0],pp=1; ord.clear(); ord.pb(ad[0]); for(int i =1;i<k;i++){ pp = (pp* pr)%mod; hash=(hash + ad[i] * pp % mod) %mod; ord.pb(ad[i]); if(!var[hash]){ // for(auto v:ord) cout<<v<<" ,";cout<<endl; for(int j=1;j<=n;j++){ dp[j]=0; } for(auto v:cc[ord[0]]){ dfs(v,0); if(dp[v]){ // cout<<v<<" == "<<dp[v]<<endl; ans=(ans+dp[v])%mod; } } var[hash]=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:22: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]
   22 |     if(idx== (ord.size()-1 ) ){
      |        ~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...