QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#478541 | #8481. Cooperative game on a tree | rania__# | RE | 645ms | 64460kb | C++23 | 2.1kb | 2024-07-15 05:16:52 | 2024-07-15 05:16:52 |
Judging History
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];
}
in main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tc=1;
// cin>>tc;
while(tc--){
std::chrono::time_point<std::chrono::system_clock> start, end;
start = std::chrono::system_clock::now();
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();i++){
end = std::chrono::system_clock::now();
std::chrono::duration<double> elapsed_seconds = end - start;
if(elapsed_seconds.count()>0.8)
break;
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: 2ms
memory: 9792kb
input:
4 1 1 3
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 7716kb
input:
3 1 2
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7716kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7864kb
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: 7928kb
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: 0ms
memory: 7624kb
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: 0ms
memory: 9696kb
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: 0ms
memory: 9768kb
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: 9972kb
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: 7704kb
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: 9864kb
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: 12336kb
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: 0
Accepted
time: 172ms
memory: 28868kb
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:
20
result:
ok 1 number(s): "20"
Test #14:
score: 0
Accepted
time: 645ms
memory: 47180kb
input:
200000 1 2 1 4 1 6 1 3 4 6 3 9 1 12 4 3 11 11 17 17 7 7 22 18 19 1 17 25 8 29 17 27 3 15 4 6 36 8 11 12 23 26 40 38 9 26 19 1 14 29 31 9 9 15 43 25 1 33 54 12 57 33 46 47 52 53 39 49 28 46 32 26 13 34 66 60 62 71 66 77 9 73 24 22 54 84 50 6 61 44 33 37 56 29 3 65 29 6 80 65 58 66 78 53 93 68 12 95 5...
output:
22
result:
ok 1 number(s): "22"
Test #15:
score: 0
Accepted
time: 611ms
memory: 46972kb
input:
200000 1 2 1 4 1 6 2 5 6 8 7 9 10 14 6 3 9 9 5 2 5 12 2 21 14 1 22 1 13 19 18 14 11 14 17 10 10 9 15 21 18 19 30 14 14 46 31 4 19 13 48 6 9 21 8 28 29 19 47 48 41 23 25 62 57 55 25 43 58 22 22 50 10 45 60 43 8 66 12 66 1 32 56 66 78 29 37 79 83 29 16 15 38 11 52 90 31 21 70 9 4 100 12 67 56 19 92 16...
output:
20
result:
ok 1 number(s): "20"
Test #16:
score: 0
Accepted
time: 602ms
memory: 47156kb
input:
200000 1 2 3 1 4 1 7 5 9 10 4 5 8 12 2 4 1 11 2 8 17 18 7 10 14 16 1 7 22 14 11 1 32 10 30 6 34 28 6 40 6 27 25 12 25 17 25 11 48 37 15 48 43 46 49 8 43 30 6 8 13 14 2 59 25 14 26 61 7 14 7 33 55 62 54 48 21 9 33 23 69 49 27 17 35 52 37 59 62 4 23 87 82 11 73 41 85 61 39 13 101 43 62 103 77 52 76 21...
output:
20
result:
ok 1 number(s): "20"
Test #17:
score: 0
Accepted
time: 637ms
memory: 46980kb
input:
200000 1 2 1 4 4 3 6 8 5 6 2 12 3 8 13 3 15 3 19 5 15 5 17 11 14 11 10 17 3 13 27 10 1 23 12 36 2 5 25 33 10 12 40 23 44 41 7 33 31 12 22 24 19 27 41 3 31 44 42 47 9 57 63 63 39 57 28 58 27 5 5 48 7 40 64 69 2 76 54 14 21 78 63 57 62 46 56 81 15 83 87 24 7 29 82 19 66 61 21 10 43 12 101 93 24 40 47 ...
output:
20
result:
ok 1 number(s): "20"
Test #18:
score: 0
Accepted
time: 625ms
memory: 47108kb
input:
200000 1 2 3 1 2 1 7 4 3 6 10 4 2 2 14 1 10 10 16 7 14 1 11 22 17 24 4 6 2 12 13 3 8 18 22 34 14 14 2 26 7 17 14 16 33 1 13 27 7 38 47 17 53 43 24 17 38 51 16 58 13 13 21 2 41 53 4 33 31 3 24 26 29 43 30 61 48 58 18 48 49 64 40 81 40 5 52 53 32 71 8 89 46 1 36 92 75 1 96 62 87 53 71 84 91 36 69 37 2...
output:
18
result:
ok 1 number(s): "18"
Test #19:
score: 0
Accepted
time: 23ms
memory: 64460kb
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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
1
result:
ok 1 number(s): "1"
Test #20:
score: -100
Runtime Error
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 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 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 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...