Submission #852800

#	Time	Username	Problem	Language	Result	Execution time	Memory
852800		Denkata	Star Trek (CEOI20_startrek)	C++14	0 / 100	1 ms	6748 KiB

startrek

#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)
                    cnt1++;
                else cnt0++;
            }
            else
            {
                if(win>0)
                    cnt1++;
                else cnt0++;
            }
        }
    }
    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)
{
    for(auto i:v[u])
    {
        if(i==p)
            continue;
        dfs3(i,u,(who^1));
        if(who==1)
            dp[1][kraen[u]]++;
        if(who==0)
        {
            if(kraen[u]==1)
                dp[1][2]++;
            if(kraen[u]==0)
                dp[1][3]++;
        }
    }
}
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);
    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])*cnt0;
    }
    cout<<dp[d][1]+dp[d][3]<<endl;

    ///d = 1
   // cout<<dp[1][0]*cnt0+dp[1][1]*cnt0+dp[1][3]*cnt1<<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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15