oj.uz

Submission #1012387

# Submission time Handle Problem Language Result Execution time Memory
1012387 2024-07-02T05:22:48 Z simona1230 Star Trek (CEOI20_startrek) C++17
38 / 100
 100 ms 16464 KB 
#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

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 / 0.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Runtime error 100 ms 14820 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct
12 Correct 33 ms 13404 KB Output is correct
13 Correct 40 ms 16464 KB Output is correct
14 Correct 26 ms 10724 KB Output is correct
15 Correct 31 ms 10588 KB Output is correct
16 Correct 29 ms 10840 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct
12 Correct 1 ms 5208 KB Output is correct
13 Incorrect 1 ms 5208 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct
12 Correct 33 ms 13404 KB Output is correct
13 Correct 40 ms 16464 KB Output is correct
14 Correct 26 ms 10724 KB Output is correct
15 Correct 31 ms 10588 KB Output is correct
16 Correct 29 ms 10840 KB Output is correct
17 Correct 1 ms 5208 KB Output is correct
18 Incorrect 1 ms 5208 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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