Submission #970863

#	Time	Username	Problem	Language	Result	Execution time	Memory
970863		pera	Paths (BOI18_paths)	C++17	100 / 100	1123 ms	184904 KiB

paths

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n , m , k , ans = 0;
vector<int> visited , color;
vector<vector<int>> g , dp , ndp;
void dfs(int u , int len){
   visited[u] = 1;
   for(int i = 0;i < g[u].size();i ++){
      for(int msk = 0;msk < (1 << k);msk ++){
         if(msk & (1 << color[u]) && __builtin_popcount(msk) == len){
            dp[u][msk] += ndp[g[u][i]][msk ^ (1 << color[u])];
         }
      }
      if(!visited[g[u][i]]){
         dfs(g[u][i] , len);
      }
   }
}
main(){
   cin >> n >> m >> k;
   color = vector<int>(n + 1);
   g = vector<vector<int>>(n + 1);
   dp = vector<vector<int>>(n + 1 , vector<int>(1 << k));
   for(int i = 1;i <= n;i ++){
      cin >> color[i];
      --color[i];
      dp[i][1 << color[i]] = 1;
   }
   for(int i = 1;i <= m;i ++){
      int u , v;
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   for(int i = 1;i < k;i ++){
      ndp = dp;
      visited = vector<int>(n + 1);
      dp = vector<vector<int>>(n + 1 , vector<int>(1 << k));
      for(int j = 1;j <= n;j ++){
         if(!visited[j]){
            dfs(j , i + 1);
         }
         for(int msk = 0;msk < (1 << k);msk ++){
            ans += dp[j][msk];
         }
      }
   }
   cout << ans << endl;
}

Compilation message (stderr)

paths.cpp: In function 'void dfs(long long int, long long int)':
paths.cpp:9:20: 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]
    9 |    for(int i = 0;i < g[u].size();i ++){
      |                  ~~^~~~~~~~~~~~~
paths.cpp: At global scope:
paths.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main(){
      | ^~~~

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30