oj.uz

Submission #1071895

# Submission time Handle Problem Language Result Execution time Memory
1071895 2024-08-23T12:11:54 Z nguyenhainam1012 Paths (BOI18_paths) C++17
53 / 100
 97 ms 34004 KB 
#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 =1e5+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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4748 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4708 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 14660 KB Output is correct
2 Correct 61 ms 14164 KB Output is correct
3 Incorrect 7 ms 28924 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4748 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4708 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 50 ms 14660 KB Output is correct
12 Correct 61 ms 14164 KB Output is correct
13 Incorrect 7 ms 28924 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 24 ms 7516 KB Output is correct
3 Correct 12 ms 7504 KB Output is correct
4 Correct 47 ms 33364 KB Output is correct
5 Correct 35 ms 33732 KB Output is correct
6 Correct 67 ms 33424 KB Output is correct
7 Correct 12 ms 7512 KB Output is correct
8 Correct 54 ms 33360 KB Output is correct
9 Correct 54 ms 33736 KB Output is correct
10 Correct 41 ms 34004 KB Output is correct
11 Correct 53 ms 20992 KB Output is correct
12 Correct 41 ms 28076 KB Output is correct
13 Correct 33 ms 21580 KB Output is correct
14 Correct 97 ms 33364 KB Output is correct
15 Correct 58 ms 33368 KB Output is correct
16 Correct 1 ms 4952 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 1 ms 4700 KB Output is correct
20 Correct 1 ms 4700 KB Output is correct
21 Correct 2 ms 4996 KB Output is correct
22 Correct 1 ms 4700 KB Output is correct
23 Correct 1 ms 4700 KB Output is correct
24 Correct 1 ms 4700 KB Output is correct
25 Correct 1 ms 4700 KB Output is correct