oj.uz

Submission #696636

# Submission time Handle Problem Language Result Execution time Memory
696636 2023-02-07T02:28:39 Z Tuanlinh123 Šarenlist (COCI22_sarenlist) C++17
110 / 110
 20 ms 2704 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/"

const ll Mod=1e9+7;

ll binpow(ll a, ll k)
{
    ll ans=1;
    while (k)
    {
        if (k%2==1)
            ans=ans*a%Mod;
        a=a*a%Mod;
        k>>=1;
    }
    return ans;
}

vector <pll> A[100005];
pll req[100005];
pll pa[100005];
ll dep[100005];

ll Pa[100005], Rank[100005];

ll Find(ll i)
{
    if (Pa[i]!=i)
        Pa[i]=Find(Pa[i]);
    return Pa[i];
}

void Union(ll a, ll b)
{
    ll PA=Find(a), PB=Find(b);
    if (PA==PB) return;
    if (Rank[PA]<Rank[PB]) swap(PA, PB);
    if (Rank[PA]==Rank[PB]) Rank[PA]++;
    Pa[PB]=PA;
}

void dfs(ll u)
{
    for (pll child:A[u])
    {
        ll v=child.fi, idx=child.se;
        if (v==pa[u].fi)
            continue;
        pa[v]={u, idx};
        dep[v]=dep[u]+1;
        dfs(v);
    }
}

void update(ll u, ll v)
{
    ll x=-1;
    while (u!=v)
    {
        if (dep[u]<dep[v]) swap(u, v);
        if (x==-1) x=pa[u].se;
        else Union(x, pa[u].se);
        u=pa[u].fi;
    }
}

int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif

    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);
    ll n, m, k; cin >> n >> m >> k;
    for (ll i=1; i<n; i++)
    {
        ll u, v; cin >> u >> v;
        A[u].pb({v, i});
        A[v].pb({u, i});
    }
    dfs(1);
    for (ll i=0; i<m; i++)
        cin >> req[i].fi >> req[i].se;
    ll ans=0;
    for (ll mask=0; mask<1<<m; mask++)
    {
        for (ll i=1; i<n; i++)
            Pa[i]=i, Rank[i]=0;
        for (ll i=0; i<m; i++)
            if (mask&1<<i)
                update(req[i].fi, req[i].se);
        ll cnt=0;
        for (ll i=1; i<n; i++)
            cnt+=Pa[i]==i;
        cnt=binpow(k, cnt);
        if (__builtin_popcount(mask)%2==0)
            ans+=cnt;
        else ans-=cnt;
        ans%=Mod; ans+=Mod; ans%=Mod;
    }
    cout << ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
65.0 / 65.0

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