Submission #1007552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007552		simona1230	Star Trek (CEOI20_startrek)	C++17	23 / 100	61 ms	16276 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);
    }
}

int cnt[100001];
int dw[100001],up[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);
        cnt[i]+=1^dw[nb];
        //if(!ldw[nb])ldw[i]=1;
    }
    if(cnt[i])dw[i]=1;
}

int lose;
int pos,key[100001];
void dfs2(int i,int p)
{
    if(cnt[p]==1&&key[p]&&!dw[i])
    {
        key[i]=1;
    }

    if(cnt[p]==0&&key[p]&&dw[i])
    {
        key[i]=1;
    }

    if(key[i]&&!dw[i])pos++;

    if(p&&up[p]==0&&(cnt[p]-(dw[i]^1))==0)up[i]=1;
    //cout<<i<<" "<<dw[i]<<" "<<up[i]<<" "<<cnt[i]<<" "<<cnt[p]-(dw[i]^1)<<endl;
    if(!dw[i]&&!up[i])lose++;
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p)continue;
        dfs2(nb,i);
    }
}
/*
za W pone edin L
za L nito edin L


*/



int main()
{
    read();
    dfs1(1,0);
    key[1]=1;
    dfs2(1,0);
    if(!dw[1])cout<<(pos*lose)%mod<<endl;
    else cout<<(n*n-pos*lose)%mod<<endl;

    return 0;
}
/*
100 1
100 44
82 150000
56 50
24 18
91 98
43 75
17 94
70 91
36 8
47 80
32 31
22 50
37 27
38 16
86 48
73 84
63 51
33 30
27 68
21 67
67 91
9 78
26 86
39 54
83 95
60 56
100 47
11 24
16 23
57 91
51 39
34 72
25 73
76 67
98 48
4 1
53 36
15 4
40 37
81 33
95 93
84 66
77 39
29 89
58 40
55 35
93 38
89 39
18 64
96 51
19 28
49 88
69 96
41 34
50 48
99 52
3 57
13 19
79 22
90 98
45 43
68 32
87 46
14 71
35 45
75 5
44 61
5 14
74 6
92 91
12 83
23 9
78 11
71 85
65 96
85 82
88 13
31 56
20 89
72 12
8 98
80 89
59 77
30 48
46 94
10 81
94 48
7 77
42 48
28 41
61 49
62 76
66 99
64 25
1 58
97 92
6 67
2 59
52 55

5 1
1 2
1 3
2 4
2 5

5 1
1 2
1 3
1 4
3 5

16 1
1 2
2 3
2 4
4 5
4 6
1 7
7 8
8 9
8 10
9 11
9 12
12 14
10 13
10 15
5 16
*/

Compilation message (stderr)

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