제출 #1071898

#제출 시각아이디문제언어결과실행 시간메모리
1071898nguyenhainam1012Paths (BOI18_paths)C++17
100 / 100
200 ms100436 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long /* #pragma omp #pragma simd #pragma unroll #pragma pack #pragma GCC optimize(3) #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC target("avx","sse2") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") */ #define int long long #define fi first #define se second #define pb push_back #define M_PI 3.14159265358979323846 #define set_on(x, i) ((x) | (1LL << i)) #define set_off(x, i) ((x) & ~(1LL << i)) #define get_bit(x, i) ((x >> i) & 1LL) #define count_bit(x) __builtin_popcountll(x) #define rep(i, a, b) for(int i=a; i<b; i++) const int maxn=1e6+5; const int mxn=1e7+5; const int N =3e5+5; int base=313,basej=431; ll MOD=1e9+7;// int mod=1e9+7; int inf=1e9; typedef pair<int, int> pii; const int S = 19; const int LOG = log2(N)+1; ll sqr(ll x) { return (x*x)%mod; } ll power(ll a, ll b) { if (b == 0) return 1 % mod; if (b % 2 == 0) return sqr(power(a, b/2)) % mod; return a * (sqr(power(a, b/2)) % mod) % mod;} int n,m,k,a[N],f[N][32];vector<int>adj[N]; void solve(){ int ans=0; for(int mask=1;mask<(1<<k);mask++){ if(count_bit(mask)==1)continue; for(int i=1;i<=n;i++){ if(get_bit(mask,a[i])==1){ for(auto v:adj[i]){ f[i][mask]+=f[v][mask^(1<<a[i])]; } } ans+=f[i][mask]; } } cout << ans; } void input(){ cin >> n >> m >> k ;for(int i=1;i<=n;i++){cin >> a[i]; a[i]--;f[i][1<<a[i]]=1;} for(int i=1;i<=m;i++){ int u,v;cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // if (fopen("LROP.inp", "r")) { // freopen("LROP.inp", "r", stdin); // freopen("LROP.out", "wN", stdout); // } int t;t=1; while(t--){ input(); solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...