oj.uz

Submission #696676

# Submission time Handle Problem Language Result Execution time Memory
696676 2023-02-07T03:32:17 Z Hiennoob123 Šarenlist (COCI22_sarenlist) C++14
110 / 110
 19 ms 592 KB 
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7;
ll n, m, k;
ll val[(1<<15)];
vector<pll> T[100];
vector<ll> Edge[20];
bool has[100];
ll s, t, type;
void dfs(ll v, ll par)
{
    if(v==t) has[v] = 1;
    for(auto u: T[v])
    {
        if(u.fi==par) continue;
        dfs(u.fi, v);
        if(has[u.fi])
        {
            has[v] = 1;
        }
    }
    //cout << has[3] << "\n";
    //cout << v << " " << has[v] << "\n";
    if(has[v])
    {
        for(auto u: T[v])
        {
            if(u.fi==par) Edge[type].push_back(u.se);
        }
    }
}
ll par[100], sz[100];
ll find_par(ll v)
{
    if(par[v]==v) return v;
    else return par[v] = find_par(par[v]);
}
void Merge(ll u, ll v)
{
    u = find_par(u); v = find_par(v);
    if(u==v) return;
    if(sz[u]<=sz[v])
    {
        sz[v]+=sz[u];
        par[u] = v;
    }
    else
    {
        sz[u]+=sz[v];
        par[v] = u;
    }
}
ll bin_pow(ll a, ll b)
{
    ll value = 1;
    while(b>0)
    {
        if(b&1) value = (value*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return value;
}
void solve_num(ll num)
{
    for(int i = 1; i<= n-1; i++)
    {
        par[i] = i;
        sz[i] = 1;
    }
    for(int i = 0; i< m; i++)
    {
        if((num&(1<<i))==0) continue;
        for(int j = 1; j< Edge[i].size(); j++)
        {
            Merge(Edge[i][j], Edge[i][j-1]);
        }
    }
    ll tong = 0;
    for(int i = 1; i<= n; i++)
    {
        if(par[i]==i) tong++;
    }
    val[num] = bin_pow(k , tong);
}
void solve()
{
    cin >> n >> m >> k;
    for(int i = 1; i< n; i++)
    {
        ll a, b; cin >> a >> b;
        T[a].push_back(mp(b, i));
        T[b].push_back(mp(a, i));
    }
    for(int i = 0; i< m; i++)
    {
        cin >> s >> t;
        for(int j = 1; j<= n; j++) has[j] = 0;
        type = i;
        dfs(s, 0);
    }
    ll ans = 0;
    for(int i = 0; i< (1<<m); i++)
    {
        solve_num(i);
        //cout << i << " " << val[i] << "\n";
        if(__builtin_popcount(i)%2==0)
        {
            ans = (ans+val[i])%mod;
        }
        else
        {
            ans = (ans-val[i])%mod;
        }
    }
    ans %= mod;
    if(ans<0) ans+= mod;
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(NULL) ; cin.tie(nullptr) ; cout.tie(nullptr);
    //freopen("B.inp","r",stdin);
    ll test_case = 1;
    while(test_case--)
    {
        solve();
    }
}

Compilation message

Main.cpp: In function 'void solve_num(long long int)':
Main.cpp:80:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int j = 1; j< Edge[i].size(); j++)
      |                        ~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #5
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 2 ms 332 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 8 ms 340 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 328 KB Output is correct
30 Correct 9 ms 340 KB Output is correct
31 Correct 3 ms 328 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 324 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 5 ms 332 KB Output is correct
36 Correct 19 ms 592 KB Output is correct
37 Correct 9 ms 340 KB Output is correct