Submission #1012387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012387		simona1230	Star Trek (CEOI20_startrek)	C++17	38 / 100	100 ms	16464 KiB

startrek

#include <bits/stdc++.h>

using namespace std;
const long long mod=1e9+7;
long long n,d;
vector<long long> v[100001];
void read()
{
    cin>>n>>d;
    for(long long i=1;i<n;i++)
    {
        long long x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}


long long num;
long long l[100001],w[100001];
void dfs1(long long i,long long p)
{
    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j];
        if(nb==p)continue;
        dfs1(nb,i);
        l[i]+=w[nb]^1;
    }
    if(l[i])w[i]=1;
}


long long c[100001],sz[100001],up[100001];
void dfs2(long long i,long long p)
{
    if(i!=1&&w[p]==0||w[p]==1&&l[p]==1&&!w[i])w[i]+=2;
    //cout<<i<<" "<<w[i]<<endl;
    if(w[i]==0)num++;

    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j];
        if(nb==p)continue;
        dfs2(nb,i);
        if(l[i]==1&&w[nb]!=1||l[i]==0)
            sz[i]+=sz[nb];
    }
    if(w[i]%2==0)sz[i]++;
    //cout<<i<<" "<<sz[i]<<endl;
}

void dfs3(long long i,long long p)
{
    long long add=up[p]+sz[p];
    if(l[p]==1&&w[i]%2==0||i!=1&&l[p]==0)
        add-=sz[i];
    up[i]=add;
    c[i]=add+sz[i];

    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j];
        if(nb==p)continue;
        dfs3(nb,i);
    }
}

long long dp[100001];
long long mult(long long x,long long y)
{
    if(y==0)return 1;
    if(y==1)return x;
    long long half=mult(x,y/2);
    if(y%2==1)return (((half*half)%mod)*x)%mod;
    return (half*half)%mod;
}


void solve()
{
    long long cl=0,cw=0;
    for(long long i=1;i<=n;i++)
        if(w[i])cw+=c[i];
        else cl+=c[i];

    dp[0]=num;
    for(long long i=1;i<=d;i++)
    {
        dp[i]=num*mult(n,2*i)-(cl-cw)*dp[i-1];
    }

    if(w[1]%2==0)cout<<(sz[1]*dp[d-1])%mod<<endl;
    else cout<<(mod+mult(n,2*d)-(sz[1]*dp[d-1])%mod)%mod<<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	dfs1(1,0);
	dfs2(1,0);
	dfs3(1,0);

	solve();
	return 0;
}

Compilation message (stderr)

startrek.cpp: In function 'void dfs1(long long int, long long int)':
startrek.cpp:24:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(long long j=0;j<v[i].size();j++)
      |                       ~^~~~~~~~~~~~
startrek.cpp: In function 'void dfs2(long long int, long long int)':
startrek.cpp:38:12: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   38 |     if(i!=1&&w[p]==0||w[p]==1&&l[p]==1&&!w[i])w[i]+=2;
      |        ~~~~^~~~~~~~~
startrek.cpp:42:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(long long j=0;j<v[i].size();j++)
      |                       ~^~~~~~~~~~~~
startrek.cpp:47:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   47 |         if(l[i]==1&&w[nb]!=1||l[i]==0)
      |            ~~~~~~~^~~~~~~~~~
startrek.cpp: In function 'void dfs3(long long int, long long int)':
startrek.cpp:57:15: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   57 |     if(l[p]==1&&w[i]%2==0||i!=1&&l[p]==0)
      |        ~~~~~~~^~~~~~~~~~~
startrek.cpp:62:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(long long j=0;j<v[i].size();j++)
      |                       ~^~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15