Submission #543826

#	Time	Username	Problem	Language	Result	Execution time	Memory
543826		Andrei_Calota	Paths (BOI18_paths)	C++14	100 / 100	832 ms	97100 KiB

paths

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
using LL = long long;
const int NMAX = 3e5;
const int KMAX = 5;

int n, m, k; vector<int> graph[1 + NMAX];
int color[1 + NMAX]; LL dp[1 + NMAX][1 << KMAX];
void read () {
    cin >> n >> m >> 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;
       graph[u].push_back ( v );
       graph[v].push_back ( u );
    }
}
void compute_dp () {
    for ( int mask = 1; mask < (1 << k); mask ++ )
       for ( int prev = 1; prev <= n; prev ++ )
          for ( auto curr : graph[prev] )
             if ( !( mask & (1 << color[curr]) ) )
               dp[curr][mask + (1 << color[curr])] += dp[prev][mask];
}
int count_bits ( int x ) {
   int answer = 0;
   while ( x ) {
      answer ++;
      x &= (x - 1);
   }
   return answer;
}
void solve () {
    LL answer = 0;
    for ( int mask = 1; mask < (1 << k); mask ++ )
       if ( count_bits ( mask ) > 1 )
         for ( int i = 1; i <= n; i ++ )
              answer += dp[i][mask];
    cout << answer;
}
int main()
{
   read (); compute_dp (); solve ();
    return 0;
}

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