Submission #716421

#	Time	Username	Problem	Language	Result	Execution time	Memory
716421		amir	Paths (BOI18_paths)	C++17	100 / 100	344 ms	53864 KiB

paths

/*
<< in the name of ALLAH >>
*/

#include <bits/stdc++.h>

//#pragma strings(readonly)
//#pragma variable(var_name,NORENT)
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops,Ofast")
//#pragma GCC target("avx2,fma")
//#pragma GCC optimize("Ofast")

using namespace std;

typedef long long int ll ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
typedef double db ;

#define ps push_back
#define pb pop_back
#define mp make_pair
#define all(x) x.begin() , x.end() 
#define sz(x) (int)x.size() 
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'
#define debugAr(a) cout << "Array " << (#a) << " :\n" ;for (int TMP : a) cout << TMP << " " ; cout << '\n' 
#define noo(x) (int)__builtin_popcount(x)
#define lastone(x) (x)&(-x)

const int maxn = 3e5 + 5 , maxk = 5 , maxb = 37 ;
int n , k  , m;
int col[maxn] ;
ll dp[maxb][maxn] ;

vector<int > adj[maxn] ;





int main()
{
    ios::sync_with_stdio(false) ; cin.tie(NULL) ; cout.tie(NULL) ;
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
    
    cin >> n >> m >> k ;
    
    for (int i = 1 ;i <= n ; i ++ ) cin >> col[i] , col[i] -- ;
    
    for (int i = 0 ;i < m ; i ++){
    	int u , v ;
    	cin >> u >> v ;
    	adj[u].ps(v) ;
    	adj[v].ps(u) ;
	}
	
	for (int i = 1 ; i <= n ; i++) adj[i].ps(0 ) ;
    
    int MX = (1 << k ) ;
    
    dp[0][0] = 1 ;
    
    for (int mask = 1 ; mask < MX ; mask ++){
    	for (int v = 1 ; v <= n ; v++){
    		if (mask & (1 << col[v])){
    			int mask2 = mask ^ (1 << col[v]) ;
    			for (int u : adj[v]){
    				dp[mask][v] += dp[mask2][u] ;
				}
			}
		}
	}
    
    ll ans = 0 ;
    
    for (int i = 1 ; i < MX ; i++){
    	if (noo(i) < 2 ) continue ;
    	for (int v = 1 ; v <= n ; v++) ans += dp[i][v] ;
	}
    cout << ans << '\n' ;
    
}

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