Submission #960937

#	Time	Username	Problem	Language	Result	Execution time	Memory
960937		batsukh2006	Paths (BOI18_paths)	C++17	100 / 100	555 ms	74324 KiB

paths

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map> 
#include<numeric>
#include<tuple>
#include<bitset>
using namespace std;
 
#define MOD 1000000007
#define int long long
#define ss second
#define ff first
#define endl '\n'
typedef pair<int,int> pp;
signed main(){
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n,m,k; cin>>n>>m>>k;
    vector<int> v[n],c(n);
    for(int i=0; i<n; i++) cin>>c[i],c[i]--;
    for(int i=0; i<m; i++){
    	int a,b; cin>>a>>b,a--,b--;
    	v[a].push_back(b);
    	v[b].push_back(a);
    }
    vector<vector<int> > dp(n,vector<int>(1<<k));
    for(int i=0; i<n; i++) dp[i][(1<<c[i])]=1;
	for(int l=2; l<=k; l++){
		for(int i=0; i<n; i++){
			for(int z=0; z<(1<<k); z++){
				if(__builtin_popcount(z)==l&&(z&(1<<c[i]))!=0){
					for(auto node: v[i]) dp[i][z]+=dp[node][z^(1<<c[i])];
				}
			}
		}
	}
	int ans=0;
	for(int i=0; i<n; i++){
		for(int z=0; z<(1<<k); z++){
			ans+=dp[i][z];
		}
	}
	cout<<ans-n;
    return 0;
}

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