oj.uz

Submission #1012379

# Submission time Handle Problem Language Result Execution time Memory
1012379 2024-07-02T05:03:45 Z simona1230 Star Trek (CEOI20_startrek) C++17
23 / 100
 33 ms 12500 KB 
#include <bits/stdc++.h>

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


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


int c[100001],sz[100001],up[100001];
void dfs2(int i,int 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(int j=0;j<v[i].size();j++)
    {
        int 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(int i,int p)
{
    int 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(int j=0;j<v[i].size();j++)
    {
        int 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(int, int)':
startrek.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
startrek.cpp: In function 'void dfs2(int, 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:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int 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(int, 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:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 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 4444 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 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct

Subtask #4
15.0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Incorrect 1 ms 4444 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 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Incorrect 33 ms 12500 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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