QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309802#8134. LCA Countingucup-team1303#AC ✓32ms13548kbC++141.7kb2024-01-20 20:51:442024-01-20 20:51:45

Judging History

你现在查看的是最新测评结果

  • [2024-01-20 20:51:45]
  • 评测
  • 测评结果:AC
  • 用时:32ms
  • 内存:13548kb
  • [2024-01-20 20:51:44]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}

const int N=2e5+5;
vector<int>G[N];
int f[N],n,ans[N],Leaf=0;
vector<int>pos;

void DP(int u){
	for(int x:G[u])DP(x);
	if(G[u].size()==0)return f[u]=1,Leaf++,void();
	if(G[u].size()==1)return f[u]=f[G[u][0]],void();
	sort(G[u].begin(),G[u].end(),[&](int x,int y){return f[x]>f[y];});
	f[u]=f[G[u][0]]+f[G[u][1]];
	for(int i=2;i<G[u].size();i++)pos.emplace_back(f[G[u][i]]);
	// cout<<"dp "<<u<<" f = "<<f[u]<<endl;
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	n=read();
	for(int i=2;i<=n;i++){int p=read();G[p].emplace_back(i);}
	DP(1);pos.emplace_back(f[1]),pos.emplace_back(0);
	sort(pos.begin(),pos.end(),[&](int x,int y){return x>y;});
	ans[1]=1;for(int i=2;i<=Leaf;i++)ans[i]=2;
	for(int i=1;i<pos.size();i++)pos[i]+=pos[i-1];
	for(int x:pos)ans[x+1]=1;
	for(int i=1;i<=Leaf;i++)ans[i]+=ans[i-1];
	for(int i=1;i<=Leaf;i++)cout<<ans[i]<<" ";puts("");

	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 8664kb

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: 2ms
memory: 8668kb

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: 2ms
memory: 8492kb

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: 2ms
memory: 9688kb

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: 2ms
memory: 8504kb

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: 2ms
memory: 9344kb

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: 2ms
memory: 9504kb

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: 0ms
memory: 8652kb

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: 2ms
memory: 8384kb

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: 20ms
memory: 11480kb

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: 26ms
memory: 11628kb

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: 30ms
memory: 13172kb

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: 32ms
memory: 13516kb

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: 22ms
memory: 13548kb

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