oj.uz

Submission #976411

# Submission time Handle Problem Language Result Execution time Memory
976411 2024-05-06T14:35:48 Z modwwe Cat Exercise (JOI23_ho_t4) C++17
100 / 100
 242 ms 58312 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void ngha();
const int mod2=1e9+7;
const int  mod1=998244353;
struct ib
{
    int a;
    int b;
};
struct icd
{
    int a,b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
//#ifndef ONLINE_JUDGE
    /// fin(task),fou(task);
//#endif
    NHP
//modwwe
    //  cin>>res;
    ngha();

}
vector<int>v[200001];
int dp[200001];
ic dsu[200001];
int st[18][200001];
int a[200001];
int d[200001];
void reset(int x)
{
    dsu[x]= {1,x,x};
}
int get(int x)
{
    if(x!=dsu[x].b)dsu[x].b=get(dsu[x].b);
    return dsu[x].b;
}
void noi(int x,int y)
{x=get(x);
y=get(y);
    if(x==y) return;
    if(dsu[x].a<dsu[y].a) swap(x,y);
    dsu[x].a+=dsu[y].a;
    dsu[y].b=x;
    dsu[x].c=min(dsu[x].c,dsu[y].c);
}
void dfs(int x,int y)
{
    st[0][x]=y;
    d[x]=d[y]+1;
    for(auto f:v[x])
    {
        if(f!=y)
        {
            dfs(f,x);
        }
    }
}
int lca(int x,int y)
{
    if(d[x]>d[y])swap(x,y);
     int ss=d[y]-d[x];
    for(int i=17;i>=0;--i)
        if(bit(ss,i))
    {
         y=st[i][y];
    }

    if(x==y) return x;
     for(int i=17;i>=0;--i)
     {
         if(st[i][y]!=st[i][x])
         {
             y=st[i][y];
             x=st[i][x];
         }
     }
     return st[0][x];
}
bool cmp(ib a,ib b){
 return a.a<b.a;
  }
/// lca(x,y)+lca(y,z)>=lca(x,z)
void ngha()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i],reset(i);
    for(int i=1; i<n; i++)
    {
        cin>>l>>r;
        v[n-a[l]+1].pb(n-a[r]+1);
        v[n-a[r]+1].pb(n-a[l]+1);
    }
    dfs(1,0);
    for(int i=1; i<18; i++)
        for(int j=1; j<=n; j++)
            st[i][j]=st[i-1][st[i-1][j]];
    for(int i=n; i>=1; i--)
    { ///cout<<i,down
        for(auto x:v[i])
        {
            if(x<i) continue;
            s2=get(x);
s2=dsu[s2].c;
        s3=lca(s2,i);
        noi(s2,i);
        dp[i]=max(dp[i],dp[s2]+d[i]+d[s2]-2*d[s3]);
        }
               }
    //cout<<lca(1,2);

    s2=0;
    for(int  i=1;i<=n;i++)
 s2=max(s2,dp[i]);
 cout<<s2;
}

Compilation message

Main.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main()
      | ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 38236 KB Output is correct
2 Correct 6 ms 38236 KB Output is correct
3 Correct 6 ms 38236 KB Output is correct
4 Correct 6 ms 38236 KB Output is correct
5 Correct 6 ms 38236 KB Output is correct
6 Correct 6 ms 38236 KB Output is correct
7 Correct 5 ms 38236 KB Output is correct
8 Correct 9 ms 38444 KB Output is correct
9 Correct 6 ms 38236 KB Output is correct
10 Correct 6 ms 38236 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 38236 KB Output is correct
2 Correct 6 ms 38236 KB Output is correct
3 Correct 6 ms 38236 KB Output is correct
4 Correct 6 ms 38236 KB Output is correct
5 Correct 6 ms 38236 KB Output is correct
6 Correct 6 ms 38236 KB Output is correct
7 Correct 5 ms 38236 KB Output is correct
8 Correct 9 ms 38444 KB Output is correct
9 Correct 6 ms 38236 KB Output is correct
10 Correct 6 ms 38236 KB Output is correct
11 Correct 6 ms 38236 KB Output is correct
12 Correct 6 ms 38232 KB Output is correct
13 Correct 6 ms 38236 KB Output is correct
14 Correct 6 ms 38436 KB Output is correct
15 Correct 6 ms 38232 KB Output is correct
16 Correct 6 ms 38236 KB Output is correct
17 Correct 5 ms 38236 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 38236 KB Output is correct
2 Correct 6 ms 38236 KB Output is correct
3 Correct 6 ms 38236 KB Output is correct
4 Correct 6 ms 38236 KB Output is correct
5 Correct 6 ms 38236 KB Output is correct
6 Correct 6 ms 38236 KB Output is correct
7 Correct 5 ms 38236 KB Output is correct
8 Correct 9 ms 38444 KB Output is correct
9 Correct 6 ms 38236 KB Output is correct
10 Correct 6 ms 38236 KB Output is correct
11 Correct 6 ms 38236 KB Output is correct
12 Correct 6 ms 38232 KB Output is correct
13 Correct 6 ms 38236 KB Output is correct
14 Correct 6 ms 38436 KB Output is correct
15 Correct 6 ms 38232 KB Output is correct
16 Correct 6 ms 38236 KB Output is correct
17 Correct 5 ms 38236 KB Output is correct
18 Correct 8 ms 38744 KB Output is correct
19 Correct 7 ms 38748 KB Output is correct
20 Correct 7 ms 38752 KB Output is correct
21 Correct 8 ms 38748 KB Output is correct
22 Correct 7 ms 38748 KB Output is correct
23 Correct 7 ms 38748 KB Output is correct
24 Correct 9 ms 38748 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 38236 KB Output is correct
2 Correct 6 ms 38236 KB Output is correct
3 Correct 6 ms 38236 KB Output is correct
4 Correct 6 ms 38236 KB Output is correct
5 Correct 6 ms 38236 KB Output is correct
6 Correct 6 ms 38236 KB Output is correct
7 Correct 5 ms 38236 KB Output is correct
8 Correct 9 ms 38444 KB Output is correct
9 Correct 6 ms 38236 KB Output is correct
10 Correct 6 ms 38236 KB Output is correct
11 Correct 6 ms 38236 KB Output is correct
12 Correct 6 ms 38232 KB Output is correct
13 Correct 6 ms 38236 KB Output is correct
14 Correct 6 ms 38436 KB Output is correct
15 Correct 6 ms 38232 KB Output is correct
16 Correct 6 ms 38236 KB Output is correct
17 Correct 5 ms 38236 KB Output is correct
18 Correct 8 ms 38744 KB Output is correct
19 Correct 7 ms 38748 KB Output is correct
20 Correct 7 ms 38752 KB Output is correct
21 Correct 8 ms 38748 KB Output is correct
22 Correct 7 ms 38748 KB Output is correct
23 Correct 7 ms 38748 KB Output is correct
24 Correct 9 ms 38748 KB Output is correct
25 Correct 6 ms 38236 KB Output is correct
26 Correct 7 ms 38748 KB Output is correct
27 Correct 7 ms 38748 KB Output is correct
28 Correct 8 ms 38748 KB Output is correct
29 Correct 7 ms 38768 KB Output is correct
30 Correct 8 ms 38492 KB Output is correct
31 Correct 7 ms 38712 KB Output is correct
32 Correct 9 ms 38492 KB Output is correct
33 Correct 8 ms 38492 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 38236 KB Output is correct
2 Correct 6 ms 38236 KB Output is correct
3 Correct 6 ms 38236 KB Output is correct
4 Correct 6 ms 38236 KB Output is correct
5 Correct 6 ms 38236 KB Output is correct
6 Correct 6 ms 38236 KB Output is correct
7 Correct 5 ms 38236 KB Output is correct
8 Correct 9 ms 38444 KB Output is correct
9 Correct 6 ms 38236 KB Output is correct
10 Correct 6 ms 38236 KB Output is correct
11 Correct 6 ms 38236 KB Output is correct
12 Correct 6 ms 38232 KB Output is correct
13 Correct 6 ms 38236 KB Output is correct
14 Correct 6 ms 38436 KB Output is correct
15 Correct 6 ms 38232 KB Output is correct
16 Correct 6 ms 38236 KB Output is correct
17 Correct 5 ms 38236 KB Output is correct
18 Correct 8 ms 38744 KB Output is correct
19 Correct 7 ms 38748 KB Output is correct
20 Correct 7 ms 38752 KB Output is correct
21 Correct 8 ms 38748 KB Output is correct
22 Correct 7 ms 38748 KB Output is correct
23 Correct 7 ms 38748 KB Output is correct
24 Correct 9 ms 38748 KB Output is correct
25 Correct 71 ms 54528 KB Output is correct
26 Correct 75 ms 58312 KB Output is correct
27 Correct 83 ms 58164 KB Output is correct
28 Correct 128 ms 56892 KB Output is correct
29 Correct 128 ms 57580 KB Output is correct
30 Correct 152 ms 57468 KB Output is correct
31 Correct 132 ms 57756 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38236 KB Output is correct
2 Correct 7 ms 38396 KB Output is correct
3 Correct 139 ms 50612 KB Output is correct
4 Correct 149 ms 50532 KB Output is correct
5 Correct 189 ms 50532 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 38236 KB Output is correct
2 Correct 6 ms 38236 KB Output is correct
3 Correct 6 ms 38236 KB Output is correct
4 Correct 6 ms 38236 KB Output is correct
5 Correct 6 ms 38236 KB Output is correct
6 Correct 6 ms 38236 KB Output is correct
7 Correct 5 ms 38236 KB Output is correct
8 Correct 9 ms 38444 KB Output is correct
9 Correct 6 ms 38236 KB Output is correct
10 Correct 6 ms 38236 KB Output is correct
11 Correct 6 ms 38236 KB Output is correct
12 Correct 6 ms 38232 KB Output is correct
13 Correct 6 ms 38236 KB Output is correct
14 Correct 6 ms 38436 KB Output is correct
15 Correct 6 ms 38232 KB Output is correct
16 Correct 6 ms 38236 KB Output is correct
17 Correct 5 ms 38236 KB Output is correct
18 Correct 8 ms 38744 KB Output is correct
19 Correct 7 ms 38748 KB Output is correct
20 Correct 7 ms 38752 KB Output is correct
21 Correct 8 ms 38748 KB Output is correct
22 Correct 7 ms 38748 KB Output is correct
23 Correct 7 ms 38748 KB Output is correct
24 Correct 9 ms 38748 KB Output is correct
25 Correct 6 ms 38236 KB Output is correct
26 Correct 7 ms 38748 KB Output is correct
27 Correct 7 ms 38748 KB Output is correct
28 Correct 8 ms 38748 KB Output is correct
29 Correct 7 ms 38768 KB Output is correct
30 Correct 8 ms 38492 KB Output is correct
31 Correct 7 ms 38712 KB Output is correct
32 Correct 9 ms 38492 KB Output is correct
33 Correct 8 ms 38492 KB Output is correct
34 Correct 71 ms 54528 KB Output is correct
35 Correct 75 ms 58312 KB Output is correct
36 Correct 83 ms 58164 KB Output is correct
37 Correct 128 ms 56892 KB Output is correct
38 Correct 128 ms 57580 KB Output is correct
39 Correct 152 ms 57468 KB Output is correct
40 Correct 132 ms 57756 KB Output is correct
41 Correct 6 ms 38236 KB Output is correct
42 Correct 7 ms 38396 KB Output is correct
43 Correct 139 ms 50612 KB Output is correct
44 Correct 149 ms 50532 KB Output is correct
45 Correct 189 ms 50532 KB Output is correct
46 Correct 108 ms 57116 KB Output is correct
47 Correct 97 ms 57132 KB Output is correct
48 Correct 105 ms 57548 KB Output is correct
49 Correct 109 ms 57108 KB Output is correct
50 Correct 215 ms 53780 KB Output is correct
51 Correct 195 ms 53776 KB Output is correct
52 Correct 242 ms 53880 KB Output is correct
53 Correct 199 ms 53780 KB Output is correct