QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#739285 | #5357. 芒果冰加了空气 | ssgzdwx | 5 | 92ms | 3960kb | C++14 | 1.1kb | 2024-11-12 21:20:21 | 2024-11-12 21:20:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5, P = 1e9 + 7;
int n;
vector<int> g[N];
bool v[N];
set<int> merge(set<int> A,set<int> B){
if (A.size() < B.size()){
for (int x : A) B.insert(x);
return B;
}
else{
for (int x : B) A.insert(x);
return A;
}
}
set<int> Find(int x,int fa){
set<int> s;
s.insert(x);
for (int y : g[x]){
if (v[y] || y == fa) continue;
s = merge(s,Find(y,x));
}
return s;
}
int doit(set<int> s){
if (s.size() == 1) return 1;
int sum = 0;
for (int x : s){
v[x] = 1;
int mul = 1;
for (int y : g[x]){
if (v[y]) continue;
mul = 1ll * mul * doit(Find(y,x)) % P;
}
(sum += mul) %= P;
v[x] = 0;
}
return sum;
}
int main(){
cin >> n;
for (int i = 1;i < n;i++){
int x,y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
cout << doit(Find(1,0));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 43ms
memory: 3692kb
input:
10 1 2 2 3 3 4 5 4 6 4 7 4 8 4 9 4 10 4
output:
310862
result:
ok single line: '310862'
Test #2:
score: 5
Accepted
time: 8ms
memory: 3604kb
input:
10 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 8 10
output:
64804
result:
ok single line: '64804'
Test #3:
score: 5
Accepted
time: 37ms
memory: 3916kb
input:
10 1 2 1 3 3 4 3 5 3 6 4 7 3 8 4 9 4 10
output:
258182
result:
ok single line: '258182'
Test #4:
score: 5
Accepted
time: 2ms
memory: 3712kb
input:
10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
output:
16796
result:
ok single line: '16796'
Test #5:
score: 5
Accepted
time: 11ms
memory: 3952kb
input:
10 1 2 2 3 3 4 4 5 1 6 2 7 3 8 4 9 5 10
output:
78384
result:
ok single line: '78384'
Test #6:
score: 5
Accepted
time: 5ms
memory: 3720kb
input:
10 1 2 1 3 2 4 3 5 2 6 4 7 3 8 7 9 9 10
output:
38896
result:
ok single line: '38896'
Test #7:
score: 5
Accepted
time: 92ms
memory: 3880kb
input:
10 1 2 2 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3
output:
609656
result:
ok single line: '609656'
Test #8:
score: 5
Accepted
time: 8ms
memory: 3656kb
input:
10 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 9 10
output:
64804
result:
ok single line: '64804'
Test #9:
score: 5
Accepted
time: 16ms
memory: 3728kb
input:
10 1 2 1 3 3 4 3 5 1 6 4 7 1 8 4 9 9 10
output:
118638
result:
ok single line: '118638'
Test #10:
score: 5
Accepted
time: 2ms
memory: 3960kb
input:
10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 8 10
output:
22438
result:
ok single line: '22438'
Test #11:
score: 5
Accepted
time: 2ms
memory: 3600kb
input:
10 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10
output:
16796
result:
ok single line: '16796'
Test #12:
score: 5
Accepted
time: 11ms
memory: 3656kb
input:
10 1 2 1 3 1 4 3 5 4 6 2 7 3 8 5 9 5 10
output:
82316
result:
ok single line: '82316'
Test #13:
score: 5
Accepted
time: 2ms
memory: 3880kb
input:
8 1 2 3 2 4 2 5 2 6 2 7 2 8 2
output:
13700
result:
ok single line: '13700'
Test #14:
score: 5
Accepted
time: 0ms
memory: 3716kb
input:
8 1 2 1 3 2 4 2 5 3 6 3 7 3 8
output:
3996
result:
ok single line: '3996'
Test #15:
score: 5
Accepted
time: 1ms
memory: 3756kb
input:
8 1 2 2 3 1 4 1 5 1 6 3 7 6 8
output:
3490
result:
ok single line: '3490'
Test #16:
score: 5
Accepted
time: 1ms
memory: 3728kb
input:
8 1 2 2 3 3 4 4 5 5 6 6 7 7 8
output:
1430
result:
ok single line: '1430'
Test #17:
score: 5
Accepted
time: 1ms
memory: 3596kb
input:
8 1 2 1 3 2 4 3 5 4 6 5 7 6 8
output:
1430
result:
ok single line: '1430'
Test #18:
score: 5
Accepted
time: 1ms
memory: 3916kb
input:
8 1 2 2 3 3 4 2 5 3 6 5 7 4 8
output:
3232
result:
ok single line: '3232'
Test #19:
score: 5
Accepted
time: 0ms
memory: 3724kb
input:
8 1 2 2 3 4 3 5 3 6 3 7 3 8 3
output:
8970
result:
ok single line: '8970'
Test #20:
score: 5
Accepted
time: 1ms
memory: 3656kb
input:
8 1 2 1 3 2 4 2 5 3 6 3 7 2 8
output:
3996
result:
ok single line: '3996'
Test #21:
score: 5
Accepted
time: 1ms
memory: 3720kb
input:
8 1 2 1 3 1 4 4 5 3 6 4 7 2 8
output:
3332
result:
ok single line: '3332'
Test #22:
score: 5
Accepted
time: 1ms
memory: 3604kb
input:
8 1 2 2 3 3 4 4 5 5 6 6 7 2 8
output:
1870
result:
ok single line: '1870'
Test #23:
score: 5
Accepted
time: 1ms
memory: 3880kb
input:
8 1 2 2 3 1 4 2 5 3 6 4 7 5 8
output:
2416
result:
ok single line: '2416'
Test #24:
score: 5
Accepted
time: 1ms
memory: 3948kb
input:
8 1 2 1 3 2 4 3 5 2 6 6 7 3 8
output:
2802
result:
ok single line: '2802'
Test #25:
score: 5
Accepted
time: 0ms
memory: 3600kb
input:
3 1 2 2 3
output:
5
result:
ok single line: '5'
Test #26:
score: 5
Accepted
time: 11ms
memory: 3728kb
input:
10 1 2 1 3 1 4 4 5 1 6 6 7 3 8 5 9 2 10
output:
78904
result:
ok single line: '78904'
Subtask #2:
score: 0
Time Limit Exceeded
Test #27:
score: 0
Time Limit Exceeded
input:
5000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #37:
score: 0
Time Limit Exceeded
input:
20 1 2 2 3 3 4 1 5 3 6 5 7 5 8 8 9 7 10 10 11 9 12 12 13 10 14 11 15 13 16 16 17 17 18 18 19 16 20
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%