제출 #1213961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213961		Dan4Life	Paths (BOI18_paths)	C++20	100 / 100	183 ms	93396 KiB

paths

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;
 
const int mxN = (int)3e5+10;
const int INF = (int)1e9;
const ll LINF = (ll)2e18;
const int MOD = 998244353;
const int mxLg = 20;

int col[mxN];
int n, m, k, ans;
int dp[mxN][1<<5];
vi adj[mxN];

int recur(int s, int mask){
	if(mask>>col[s]&1) return 0;
	if(dp[s][mask]!=-1) return dp[s][mask];
	dp[s][mask] = 1;
	for(auto u : adj[s])
		dp[s][mask]+=recur(u,mask^(1<<col[s]));
	return dp[s][mask];
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> k;
    memset(dp,-1,sizeof(dp));
    for(int i = 1; i <= n; i++) 
		cin >> col[i], col[i]--;
    for(int i = 0; i < m; i++){
		int a, b; cin >> a >> b;
		if(col[a]!=col[b]) adj[a].pb(b), adj[b].pb(a);
	}
	for(int i = 1; i <= n; i++) ans+=recur(i,0);
	cout << ans-n << "\n";
}

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