Submission #1012379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012379		simona1230	Star Trek (CEOI20_startrek)	C++17	23 / 100	33 ms	12500 KiB

startrek

#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 (stderr)

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
• Subtask 2: 0 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15