oj.uz

Submission #852816

# Submission time Handle Problem Language Result Execution time Memory
852816 2023-09-22T18:39:36 Z Denkata Star Trek (CEOI20_startrek) C++14
0 / 100
 8 ms 8880 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int maxd = 1e5+3;
const int maxn = 1e5+3;
ll i,j,p,q,n,m,k,d,ans,dp[maxd][4],cnt1,cnt0,br[maxn][2],kraen[maxn],dist[maxn],winner[maxn],tek[maxn];
vector <int> v[maxn];
void dfs(int u,int p)
{
    kraen[u] = 0;
    for(auto i:v[u])
    {
        if(i==p)continue;
        dist[i] = dist[u]+1;
        dfs(i,u);
        if(kraen[i]==0)
            kraen[u] = 1;
    }
}
void dfs2(int u,int p)
{
    tek[u] = 0;
    for(auto i:v[u])
    {
        if(i==p)continue;
        dfs2(i,u);
        if(tek[i]==0)
            tek[u] = 1;
    }
}
void dfs3(int u,int p,int who)
{
    if(who==1)
        dp[1][kraen[u]]++;
    if(who==0)
    {
        if(kraen[u]==1)
            dp[1][2]++;
        if(kraen[u]==0)
            dp[1][3]++;
    }
    for(auto i:v[u])
    {
        if(i==p)
            continue;
        dfs3(i,u,(who^1));
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>d;
    d++;
    for(i=1; i<n; i++)
    {
        cin>>p>>q;
        v[p].push_back(q);
        v[q].push_back(p);
    }
    dfs(1,0);
    /**
    for(i=1;i<=n;i++)
        cout<<i<<" : "<<kraen[i]<<endl;
    */
    for(i=1;i<=n;i++)
    {
        dfs2(i,0);
        if(tek[i]==1)
            winner[i] = 1,cnt1++;
        else winner[i] = 0,cnt0++;
        //cout<<winner[i]<<endl;
    }
    dfs3(1,0,1);
    //cout<<cnt0<<" "<<cnt1<<endl;
    for(i=2; i<=d; i++)
    {
        dp[i][1] = dp[i-1][3]*cnt1+(dp[i-1][0]+dp[i-1][1])*cnt0;
        dp[i][2] = dp[i-1][0]*cnt1+(dp[i-1][2]+dp[i-1][3])*cnt0;
        dp[i][0] = dp[i-1][0]*cnt1+(dp[i-1][2]+dp[i-1][3])*cnt0;
        dp[i][3] = dp[i-1][3]*cnt1+(dp[i-1][0]+dp[i-1][1])*cnt1;
    }
    //cout<<dp[1][0]<<" "<<dp[1][1]<<" "<<dp[1][2]<<" "<<dp[1][3]<<endl;
    cout<<(dp[1][1]+dp[1][0])*cnt0<<endl;

    ///
    return 0;
}
/**
12 2
1 2
2 4
2 5
5 8
1 3
3 6
3 7
6 9
7 10
10 11
10 12
*/

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Incorrect 8 ms 8880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Incorrect 2 ms 8796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Incorrect 2 ms 8796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Incorrect 2 ms 8796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Incorrect 2 ms 8796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Incorrect 2 ms 8796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Incorrect 8 ms 8880 KB Output isn't correct
3 Halted 0 ms 0 KB -