oj.uz

Submission #1107734

# Submission time Handle Problem Language Result Execution time Memory
1107734 2024-11-02T04:11:14 Z ToTenLinh Šarenlist (COCI22_sarenlist) C++17
110 / 110
 2 ms 4944 KB 
#include <bits/stdc++.h>
#define fo(i,m,n) for(int i=m;i<=n;i++)
#define fod(i,n,m) for(int i=n;i>=m;i--)
#define fo1(i,m,n,k) for(int i=m;i<=n;i=i+k)
#define fod1(i,n,m,k) for(int i=n;i>=m;i=i-k)
#define fol(i,m,n) for(long long i=m;i<=n;i++)
#define fodl(i,n,m) for(long long i=n;i>=m;i--)
#define fo1l(i,m,n,k) for(long long i=m;i<=n;i=i+k)
#define fod1l(i,n,m,k) for(long long i=n;i>=m;i=i-k)
#define lb lower_bound
#define ub upper_bound
#define pii pair <int,int>
#define vii vector<pii>
#define ll long long
#define fi first
#define se second
#define si size()
#define pb push_back
#define ppb pop_back()
#define fr front()
#define et empty()
#define bg begin()
#define ub upper_bound
#define lb lower_bound
#define ed end()
#define el endl
#define EL cout << '\n';
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
const int M = 1e3 + 5;
ll bit[16], ktra[1 << 15][16], val[1 << 15], indx[62];
int n, m, k, sz[1 << 15];
pii p[72];
vii adj[72];
void dfs(int v, int par){
    for(pii it : adj[v]){
        if(it.fi == par) continue;
        p[it.fi] = {v, it.se};
        dfs(it.fi, v);
    }
}
void solve(){
    cin >> n >> m >> k;
    fo(i, 0, n - 2){
        int a, b;
        cin >> a >> b;
        --a, --b;
        adj[a].pb({b, i}), adj[b].pb({a, i});
    }
    fo(i, 0, m - 1){
        int a, b;
        cin >> a >> b;
        --a, --b;
        dfs(a, a);
        while(b != a){
            bit[i] |= (1LL << (p[b].se));
            b = p[b].fi;
        }
    }
    indx[0] = 1;
    fo(i, 0, n - 1) indx[i + 1] = (indx[i] * k) % mod;
    ll ans = indx[n - 1];
    fo(mask, 1, (1 << m) - 1){
        int ind = __builtin_ctz(mask);
        int pr = mask - (1 << ind);
        ll edl = bit[ind], cur = edl;
        val[mask] = val[pr] | edl;
        fo(i, 0, sz[pr] - 1){
            if(ktra[pr][i] & edl) cur |= ktra[pr][i];
            else ktra[mask][sz[mask]++] = ktra[pr][i];
        }
        ktra[mask][sz[mask]++] = cur;
        int choice = sz[mask] + (n - 1 - __builtin_popcountll(val[mask]));
        int add = (__builtin_popcount(mask) & 1) ? -indx[choice] : indx[choice];
        ans = (ans + add + mod) % mod;
    }
    cout << ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 2 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2616 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2552 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2552 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct

Subtask #5
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 2 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2616 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 1 ms 2384 KB Output is correct
12 Correct 1 ms 2384 KB Output is correct
13 Correct 1 ms 2384 KB Output is correct
14 Correct 1 ms 2384 KB Output is correct
15 Correct 1 ms 2384 KB Output is correct
16 Correct 1 ms 2384 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct
18 Correct 1 ms 2384 KB Output is correct
19 Correct 1 ms 2552 KB Output is correct
20 Correct 1 ms 2552 KB Output is correct
21 Correct 1 ms 2384 KB Output is correct
22 Correct 1 ms 2384 KB Output is correct
23 Correct 1 ms 2384 KB Output is correct
24 Correct 1 ms 2384 KB Output is correct
25 Correct 1 ms 2384 KB Output is correct
26 Correct 1 ms 2384 KB Output is correct
27 Correct 1 ms 4432 KB Output is correct
28 Correct 1 ms 2384 KB Output is correct
29 Correct 1 ms 2384 KB Output is correct
30 Correct 2 ms 4688 KB Output is correct
31 Correct 1 ms 2384 KB Output is correct
32 Correct 1 ms 2384 KB Output is correct
33 Correct 1 ms 2384 KB Output is correct
34 Correct 1 ms 2384 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 1 ms 4944 KB Output is correct
37 Correct 1 ms 4688 KB Output is correct