Submission #1071898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071898		nguyenhainam1012	Paths (BOI18_paths)	C++17	100 / 100	200 ms	100436 KiB

paths

#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();
    }
}

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