oj.uz

Submission #1012380

# Submission time Handle Problem Language Result Execution time Memory
1012380 2024-07-02T05:04:24 Z simona1230 Star Trek (CEOI20_startrek) C++17
38 / 100
 40 ms 17136 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]!=1||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);
    }
}

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

	if(w[1]%2==0)cout<<(sz[1]*num)%mod<<endl;
	else cout<<(mod+n*n-(sz[1]*num)%mod)%mod<<endl;
	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]!=1||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 2 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 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 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

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

Subtask #4
15.0 / 15.0

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

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6316 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 40 ms 12688 KB Output is correct
13 Correct 40 ms 17136 KB Output is correct
14 Correct 27 ms 11084 KB Output is correct
15 Correct 34 ms 11264 KB Output is correct
16 Correct 35 ms 11280 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6316 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Incorrect 1 ms 6488 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 6492 KB Output is correct
2 Correct 1 ms 6316 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 40 ms 12688 KB Output is correct
13 Correct 40 ms 17136 KB Output is correct
14 Correct 27 ms 11084 KB Output is correct
15 Correct 34 ms 11264 KB Output is correct
16 Correct 35 ms 11280 KB Output is correct
17 Correct 2 ms 6492 KB Output is correct
18 Incorrect 1 ms 6488 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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