oj.uz

Submission #852806

# Submission time Handle Problem Language Result Execution time Memory
852806 2023-09-22T18:09:39 Z Denkata Star Trek (CEOI20_startrek) C++14
0 / 100
 2 ms 6744 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];
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 par,int win,int lose)
{
    //cout<<u<<" "<<par<<endl;
    if(u!=1)
    {
        if(kraen[u]==1)
            cnt1++;
        else
        {
            p = dist[u];
            if(p%2==1)
            {
                if(lose>0)///root wins => only winners around me
                    cnt0++;
                else cnt1++;///otherwise root loses => loser around me => I win
            }
            else
            {
                if(lose>0)///root wins => loser around me => I win
                    cnt1++;
                else cnt0++;///otherwise root loses => loser around me => I win
            }
        }
    }
    for(auto i:v[u])
    {
        if(i==par)
            continue;
        if(u==1)
            dfs2(i,u,win-(kraen[i]==1),lose-(kraen[i]==0));
        else dfs2(i,u,win,lose);
    }
}
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(auto i:v[1])
    {
        if(kraen[i]==1)
            br[1][1]++;
        else br[1][0]++;
    }
    if(kraen[1]==1)
        cnt1++;
    else cnt0++;
    dfs2(1,0,br[1][1],br[1][0]);
    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[d][1]<<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 6744 KB Output is correct
2 Incorrect 2 ms 6744 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 6744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Incorrect 1 ms 6744 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 6744 KB Output is correct
2 Incorrect 2 ms 6744 KB Output isn't correct
3 Halted 0 ms 0 KB -