oj.uz

Submission #1007553

# Submission time Handle Problem Language Result Execution time Memory
1007553 2024-06-25T07:29:53 Z simona1230 Star Trek (CEOI20_startrek) C++17
38 / 100
 51 ms 15184 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 cnt[100001];
long long dw[100001],up[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);
        cnt[i]+=1^dw[nb];
        //if(!ldw[nb])ldw[i]=1;
    }
    if(cnt[i])dw[i]=1;
}

long long lose;
long long pos,key[100001];
void dfs2(long long i,long long 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(long long j=0;j<v[i].size();j++)
    {
        long long 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(long long int, long long int)':
startrek.cpp:22: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]
   22 |     for(long long j=0;j<v[i].size();j++)
      |                       ~^~~~~~~~~~~~
startrek.cpp: In function 'void dfs2(long long int, long long int)':
startrek.cpp:52: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]
   52 |     for(long long j=0;j<v[i].size();j++)
      |                       ~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #4
15.0 / 15.0

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

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 1 ms 3672 KB Output is correct
8 Correct 1 ms 3676 KB Output is correct
9 Correct 1 ms 3676 KB Output is correct
10 Correct 1 ms 3676 KB Output is correct
11 Correct 1 ms 3672 KB Output is correct
12 Correct 50 ms 11760 KB Output is correct
13 Correct 51 ms 15184 KB Output is correct
14 Correct 42 ms 9424 KB Output is correct
15 Correct 49 ms 10324 KB Output is correct
16 Correct 44 ms 10576 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 1 ms 3672 KB Output is correct
8 Correct 1 ms 3676 KB Output is correct
9 Correct 1 ms 3676 KB Output is correct
10 Correct 1 ms 3676 KB Output is correct
11 Correct 1 ms 3672 KB Output is correct
12 Correct 1 ms 3672 KB Output is correct
13 Incorrect 1 ms 3676 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 3676 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct
6 Correct 1 ms 3676 KB Output is correct
7 Correct 1 ms 3672 KB Output is correct
8 Correct 1 ms 3676 KB Output is correct
9 Correct 1 ms 3676 KB Output is correct
10 Correct 1 ms 3676 KB Output is correct
11 Correct 1 ms 3672 KB Output is correct
12 Correct 50 ms 11760 KB Output is correct
13 Correct 51 ms 15184 KB Output is correct
14 Correct 42 ms 9424 KB Output is correct
15 Correct 49 ms 10324 KB Output is correct
16 Correct 44 ms 10576 KB Output is correct
17 Correct 1 ms 3672 KB Output is correct
18 Incorrect 1 ms 3676 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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