QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #308874 | #8134. LCA Counting | ucup-team2303# | AC ✓ | 45ms | 59400kb | C++14 | 2.3kb | 2024-01-20 13:29:35 | 2024-01-20 13:29:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long T,a,b,c,d[1000001],v[1000001],o,h[1000001],fa[1000001],q,w,e,an[1000001],cn,fac[1000001],inv[1000001],st[1000001],u[1000001],dp[1000001],si[1000001];
char s[1000001];
struct p{long long q,w;bool operator < (const p &aa) const{return w<aa.w;};}l[1000001],nx[1000001];
long long pow_(long long qq,long long ww){long long ee=1;while(ww){if(ww&1) ee*=qq,ee%=mod;qq*=qq,qq%=mod,ww>>=1;}return ee%mod;}
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*f;}
void add(long long qq,long long ww){l[++o].q=ww,l[o].w=h[qq],h[qq]=o;}
long long gcd(long long qq,long long ww){return !ww?qq:gcd(ww,qq%ww);}
long long find(long long qq){return qq==fa[qq]?qq:fa[qq]=find(fa[qq]);}
void merge(long long qq,long long ww){long long f1=find(qq),f2=find(ww);if(f1==f2) return;fa[f1]=f2;}
long long C(long long qq,long long ww){return fac[qq]*inv[ww]%mod*inv[qq-ww]%mod;}
priority_queue<p> qu;
void dfs(long long qq,long long ww)
{
fa[qq]=ww;
long long hh=0,mx1=0,mx2=0,id1=0,id2=0;
for(int i=h[qq];i;i=l[i].w)
{
if(l[i].q!=ww)
{
hh=1;
dfs(l[i].q,qq);
si[qq]+=si[l[i].q];
if(dp[l[i].q]>mx1) mx2=mx1,id2=id1,mx1=dp[l[i].q],id1=l[i].q;
else if(dp[l[i].q]>mx2) mx2=dp[l[i].q],id2=l[i].q;
}
}
nx[qq]=p{id1,id2};
dp[qq]=mx1+mx2;
if(!hh) si[qq]=1,dp[qq]=1;
}
void dfs1(long long qq,long long ww)
{
v[qq]=1;
for(int i=h[qq];i;i=l[i].w)
{
if(l[i].q!=ww)
{
if(l[i].q==nx[qq].q||l[i].q==nx[qq].w)
{
dfs1(l[i].q,qq);
}
else qu.push(p{l[i].q,dp[l[i].q]});
}
}
}
int main()
{
// freopen("1.in","r",stdin);
srand((unsigned)(time(0)^(*new int)));
fac[0]=1;for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
inv[1000000]=pow_(fac[1000000],mod-2);for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
T=1;
scanf("%lld",&a);
for(int i=2;i<=a;i++)
{
d[i]=read();
add(i,d[i]),add(d[i],i);
}dfs(1,0);
qu.push(p{1,dp[1]});
long long sm=0;
while(!qu.empty())
{
p r=qu.top();qu.pop();
if(v[r.q]) continue;
sm+=dp[r.q];an[sm+1]--;
dfs1(r.q,fa[r.q]);
}
for(int i=1;i<=a;i++) an[i]+=an[i-1];
for(int i=1;i<=si[1];i++) printf("%lld ",an[i]+i*2-1);
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 32612kb
input:
7 1 1 2 4 2 2
output:
1 3 5 6
result:
ok 4 number(s): "1 3 5 6"
Test #2:
score: 0
Accepted
time: 9ms
memory: 30540kb
input:
10 1 1 2 2 1 1 1 2 4
output:
1 3 5 6 7 8 9
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 10ms
memory: 30628kb
input:
10 1 2 2 4 5 6 1 2 4
output:
1 3 5 7 8
result:
ok 5 number(s): "1 3 5 7 8"
Test #4:
score: 0
Accepted
time: 10ms
memory: 30488kb
input:
10 1 2 3 3 3 5 6 4 9
output:
1 3 4
result:
ok 3 number(s): "1 3 4"
Test #5:
score: 0
Accepted
time: 4ms
memory: 30680kb
input:
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 4 1 2 2 1 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 6 3 1 1 1 2 2 1 1 2 1 2 1 3 1 2 1 1 2 1 1 1 1 1 1 1 4 1 5 1 1 1 1 1 2 1 1 2 1 2 1 2 5 3 1 3 1 1 2 1 2 1 1 3 2 1 6 2 1 2 5 1 1 1 3 2 1 2 1 1 1 1 1...
output:
1 3 5 7 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 82 83 85 86 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 12...
result:
ok 962 numbers
Test #6:
score: 0
Accepted
time: 9ms
memory: 32724kb
input:
1000 1 1 1 1 1 1 1 2 2 1 2 3 1 1 1 2 2 1 1 1 2 1 2 3 8 2 2 2 8 1 6 3 1 1 1 4 2 14 8 2 1 1 1 3 1 4 1 1 3 11 1 1 2 2 3 2 5 5 6 5 3 3 10 5 3 1 9 14 3 19 4 15 4 3 3 10 3 10 5 1 2 12 7 13 3 9 6 19 9 6 4 3 5 28 10 16 8 12 39 1 11 12 2 2 10 15 5 28 10 4 4 5 5 18 15 15 11 5 25 7 2 10 1 24 8 15 14 11 38 9 9 ...
output:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 28 30 32 34 36 37 39 41 43 44 46 48 50 51 53 55 57 58 60 62 64 65 67 69 71 72 74 76 78 79 81 83 85 86 88 90 92 93 95 97 99 100 102 104 105 107 109 110 112 114 115 117 119 120 122 124 125 127 129 130 132 133 135 136 138 139 141 142 144 145 147 148 150 151 153 154 ...
result:
ok 822 numbers
Test #7:
score: 0
Accepted
time: 15ms
memory: 32572kb
input:
1000 1 2 2 2 1 4 3 6 7 5 8 8 1 12 12 16 4 16 18 3 17 22 7 22 9 17 21 16 16 18 29 31 12 29 32 36 22 31 32 14 15 13 8 1 36 19 33 2 10 28 29 1 53 27 15 56 34 57 21 15 58 36 57 57 16 45 16 51 44 18 31 52 53 34 65 30 51 8 59 72 53 49 49 35 31 23 3 19 69 5 16 11 45 12 62 23 46 5 24 61 63 81 1 85 73 53 84 ...
output:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177...
result:
ok 487 numbers
Test #8:
score: 0
Accepted
time: 6ms
memory: 30580kb
input:
1000 1 2 3 4 5 6 7 7 8 9 11 12 13 14 14 15 17 15 17 20 19 22 22 23 24 25 22 26 23 30 29 32 32 33 33 34 30 35 39 21 41 28 42 42 44 44 38 48 49 50 51 52 44 51 44 53 36 52 59 48 55 62 63 54 65 59 54 67 60 65 68 71 71 74 58 73 65 78 76 70 77 82 80 57 85 81 86 80 79 81 78 88 88 86 61 93 88 96 98 100 96 9...
output:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177...
result:
ok 374 numbers
Test #9:
score: 0
Accepted
time: 7ms
memory: 32592kb
input:
1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 36 38 39 40 41 42 42 44 45 46 47 48 49 50 51 52 53 54 54 56 57 58 59 60 61 62 62 62 65 66 66 68 69 70 71 72 73 73 75 75 76 78 78 80 79 80 83 83 85 86 86 88 88 90 91 91 92 94 94 96 97 98 95 97 100 ...
output:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177...
result:
ok 319 numbers
Test #10:
score: 0
Accepted
time: 40ms
memory: 59400kb
input:
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1 1 1 1 1 1 1 1 3 1 2 2 1 6 1 1 2 1 3 1 1 1 1 1 2 2 1 2 1 1 1 2 5 1 2 1 1 1 1 1 1 2 3 2 1 1 1 1 1 2 1 1 2 1 2 1 2 1 1 1 3 4 2 1 3 2 2 1 1 3 1 2 1 2 4 3 2 3 1 1 2 1 5 1 3...
output:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 32 34 36 38 40 42 44 46 47 49 51 53 55 57 59 61 62 64 66 68 70 72 74 75 77 79 81 83 85 86 88 90 92 94 95 97 99 101 102 104 106 108 109 111 113 115 116 118 120 122 123 125 127 129 130 132 134 136 137 139 141 143 144 146 148 150 151 153 155 157 158 160 162 16...
result:
ok 192712 numbers
Test #11:
score: 0
Accepted
time: 45ms
memory: 53656kb
input:
200000 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 4 1 1 1 1 1 7 3 1 1 1 2 2 3 3 2 3 5 2 1 1 3 1 1 1 5 2 4 1 1 2 1 8 4 11 2 6 2 3 1 11 6 1 4 5 9 5 1 1 10 1 3 4 1 24 3 1 27 4 10 9 5 2 4 5 13 5 3 1 7 4 1 9 20 17 3 16 1 2 3 3 15 2 19 5 11 3 4 14 2 11 15 4 21 9 15 3 7 9 5 3 21 2 10 7 13 26 19 7 1 16 3 14 2 9 30 16 ...
output:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177...
result:
ok 165619 numbers
Test #12:
score: 0
Accepted
time: 38ms
memory: 51784kb
input:
200000 1 2 3 2 3 4 6 4 5 1 2 2 7 6 3 12 13 10 8 8 12 9 11 14 19 24 14 4 27 11 1 19 22 10 19 27 33 4 10 29 33 19 35 37 29 31 29 45 32 40 33 50 28 21 19 19 9 46 31 36 9 45 17 52 40 4 23 26 11 67 22 47 2 48 48 8 71 18 23 44 41 17 80 25 41 33 39 16 7 23 47 27 67 47 32 65 35 69 29 60 87 21 68 4 87 106 16...
output:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177...
result:
ok 99943 numbers
Test #13:
score: 0
Accepted
time: 41ms
memory: 52264kb
input:
200000 1 2 3 4 4 6 6 8 8 9 11 12 13 14 15 15 17 18 19 18 16 21 22 22 24 25 21 25 26 30 28 29 32 31 33 36 36 38 37 39 31 41 42 43 42 45 44 48 41 35 43 49 50 52 51 53 57 57 57 60 60 54 62 62 64 64 63 66 68 70 61 67 69 64 75 65 76 75 63 78 79 64 77 84 81 80 81 82 83 85 76 78 86 94 94 96 97 92 86 94 92 ...
output:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177...
result:
ok 76008 numbers
Test #14:
score: 0
Accepted
time: 35ms
memory: 54060kb
input:
200000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 46 48 49 50 51 52 52 54 55 55 57 58 58 59 61 62 62 64 65 65 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 83 83 85 87 88 89 88 91 92 93 94 92 94 95 98 99 100 9...
output:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177...
result:
ok 73621 numbers
Extra Test:
score: 0
Extra Test Passed