oj.uz

Submission #1007552

# Submission time Handle Problem Language Result Execution time Memory
1007552 2024-06-25T07:28:34 Z simona1230 Star Trek (CEOI20_startrek) C++17
23 / 100
 61 ms 16276 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);
    }
}

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

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

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

Subtask #4
15.0 / 15.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 4188 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 4140 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 1 ms 4188 KB Output is correct
9 Correct 1 ms 4188 KB Output is correct
10 Correct 1 ms 4188 KB Output is correct
11 Correct 1 ms 4208 KB Output is correct
12 Correct 53 ms 12116 KB Output is correct
13 Correct 61 ms 16276 KB Output is correct
14 Incorrect 35 ms 8652 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 4188 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 4140 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 1 ms 4188 KB Output is correct
9 Correct 1 ms 4188 KB Output is correct
10 Correct 1 ms 4188 KB Output is correct
11 Correct 1 ms 4208 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Incorrect 1 ms 4188 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 3932 KB Output is correct
2 Correct 1 ms 3932 KB Output is correct
3 Correct 1 ms 4188 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 4140 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 1 ms 4188 KB Output is correct
9 Correct 1 ms 4188 KB Output is correct
10 Correct 1 ms 4188 KB Output is correct
11 Correct 1 ms 4208 KB Output is correct
12 Correct 53 ms 12116 KB Output is correct
13 Correct 61 ms 16276 KB Output is correct
14 Incorrect 35 ms 8652 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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