QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#478540#8481. Cooperative game on a treerania__#WA 225ms28508kbC++231.9kb2024-07-15 05:15:162024-07-15 05:15:16

Judging History

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

  • [2024-07-15 05:15:16]
  • 评测
  • 测评结果:WA
  • 用时:225ms
  • 内存:28508kb
  • [2024-07-15 05:15:16]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
#define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceill(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?0:1))
#define floorr(x,y) ((x/y)+(x%y!=0)*(x/abs(x)*y/abs(y)<0?-1:0))
#define YN(x) cout<<(x?"YES\n":"NO\n");
#define Yn(x) cout<<(x?"Yes\n":"No\n");
#define yn(x) cout<<(x?"yes\n":"no\n");
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;

int n,dist[200010],depth[200010],b[200010][20];
vector<int> v[200010];
int dfs(int idx,int par,int d=1){
	dist[idx]=MAAX;
	depth[idx]=d;
	b[idx][0]=par;
	for(int i=1;i<20;i++)
		b[idx][i]=b[b[idx][i-1]][i-1];
	for(int i=0;i<v[idx].size();i++){
		if(v[idx][i]==par)
			continue;
		dist[idx]=min(dfs(v[idx][i],idx,d+1),dist[idx]);
	}
	if(v[idx].size()==0)
		dist[idx]=0;
	return dist[idx]+1;
}
int up(int idx,int x){
	if(x==0)
		return idx;
	return up(b[idx][__lg(x)],x-(1<<__lg(x)));
}
int lca(int x,int y){
	if(depth[x]<depth[y])
		swap(x,y);
	x=up(x,depth[x]-depth[y]);
	for(int i=19;i>=0;i--){
		if(b[x][i]!=b[y][i]){
			x=b[x][i];
			y=b[y][i];
		}
	}
	return b[x][0];
}
int fun(int idx,int tar){
	if(idx==tar)
		return 0;
	return fun(up(tar,depth[tar]-depth[idx]-dist[idx]),tar)+1;
}
bool comp(int x,int y){
	return depth[x]>=depth[y];
}
int t;

in main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc=1;
    // cin>>tc;
    while(tc--){
    	t=time(0);
		cin>>n;
		for(int i=2;i<=n;i++){
			int x;
			cin>>x;
			v[x].pb(i);
		}
		dfs(1,0);
		vector<int> vec;
		for(int i=1;i<=n;i++){
			if(v[i].size())
				continue;
			vec.pb(i);
		}
		sort(vec.begin(),vec.end(),comp);
		int ans=0;
		for(int i=0;i<vec.size()&&time(0)==t;i++){
			ans=max(ans,fun(1,vec[i]));
		}
		cout<<ans<<"\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7784kb

input:

4
1 1 3

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 9804kb

input:

3
1 2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 7724kb

input:

2
1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 9872kb

input:

10
1 2 3 1 4 4 7 8 9

output:

3

result:

ok 1 number(s): "3"

Test #5:

score: 0
Accepted
time: 1ms
memory: 9972kb

input:

10
1 2 1 4 5 5 7 7 8

output:

4

result:

ok 1 number(s): "4"

Test #6:

score: 0
Accepted
time: 1ms
memory: 7760kb

input:

10
1 1 3 3 5 5 6 4 1

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 1ms
memory: 7784kb

input:

10
1 2 3 4 3 6 3 6 7

output:

3

result:

ok 1 number(s): "3"

Test #8:

score: 0
Accepted
time: 1ms
memory: 9792kb

input:

10
1 2 3 3 2 3 5 1 7

output:

4

result:

ok 1 number(s): "4"

Test #9:

score: 0
Accepted
time: 1ms
memory: 7764kb

input:

10
1 2 3 4 5 6 7 8 9

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 1ms
memory: 7784kb

input:

100
1 2 1 1 3 6 5 5 4 8 4 4 3 14 10 14 8 13 12 18 8 3 7 1 12 10 9 17 26 30 21 11 29 19 20 25 17 10 9 26 6 40 42 29 2 24 14 25 6 41 47 24 21 46 28 8 30 2 19 41 54 43 23 1 65 21 19 35 58 8 71 59 12 2 13 4 16 7 22 58 26 44 1 12 14 80 19 12 43 77 21 54 41 94 37 61 28 82 30

output:

6

result:

ok 1 number(s): "6"

Test #11:

score: 0
Accepted
time: 2ms
memory: 9884kb

input:

1000
1 1 1 4 2 3 5 1 7 6 6 12 11 8 6 2 15 18 17 6 21 14 14 3 21 20 1 23 1 3 31 19 26 13 32 24 31 29 23 4 10 16 24 27 28 33 19 39 39 46 40 28 9 7 53 28 13 26 41 52 51 12 60 5 37 7 39 37 21 24 18 67 42 27 42 70 31 8 17 71 58 36 39 38 35 78 34 2 18 67 47 58 11 91 92 36 97 51 44 41 25 21 73 15 45 105 9 ...

output:

10

result:

ok 1 number(s): "10"

Test #12:

score: 0
Accepted
time: 6ms
memory: 12624kb

input:

10000
1 2 1 3 5 3 5 3 9 8 4 9 11 5 14 8 16 3 4 19 7 10 16 8 15 8 26 14 10 18 3 16 21 12 17 11 20 23 38 4 31 39 38 31 31 22 21 25 5 13 12 43 9 18 28 21 1 19 47 40 12 19 38 60 20 59 63 27 1 66 7 68 1 44 5 53 11 10 40 33 38 26 2 59 8 61 34 1 38 15 57 13 62 60 10 16 32 76 43 10 72 29 91 43 27 65 8 42 19...

output:

20

result:

ok 1 number(s): "20"

Test #13:

score: -100
Wrong Answer
time: 225ms
memory: 28508kb

input:

100000
1 1 3 1 5 5 4 5 7 9 10 4 13 4 14 10 15 7 1 18 13 4 3 10 21 9 12 21 25 4 13 8 33 13 16 34 32 29 8 28 31 1 28 30 29 28 17 16 14 8 1 38 47 9 40 4 1 3 25 6 34 38 6 58 25 25 56 57 39 18 15 58 66 4 18 58 21 24 62 77 71 39 46 24 39 44 19 77 61 76 63 78 93 9 5 50 26 58 56 2 35 3 22 13 104 65 68 57 45...

output:

0

result:

wrong answer 1st numbers differ - expected: '20', found: '0'