oj.uz

Submission #963523

# Submission time Handle Problem Language Result Execution time Memory
963523 2024-04-15T09:12:18 Z vladburac Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 186 ms 64516 KB 
// credit: valeriu
#include <bits/stdc++.h>
using namespace std;
#define pii pair<long long, long long>
using ll = long long;
const int NMAX = 5e5;
const int VALMAX = 1e6;
const int LOGMAX = 18;
const int INF = 1e9;
const int MOD = 998244353;
mt19937 rnd( chrono::steady_clock::now().time_since_epoch().count() );

/*
#ifndef HOME
  ifstream fin( "regate.in" );
  ofstream fout( "regate.out" );
  #define cin fin
  #define cout fout
#endif // HOME
*/

vector <int> edges[NMAX+1];
pii h[NMAX+1];
int parent[NMAX+1];
int heavy[NMAX+1];

int find( int node ) {
  if( parent[node] == node )
    return node;
  return parent[node] = find( parent[node] );
}
void unite( int a, int b ) {
  a = find( a );
  b = find( b );
  if( a != b ) {
    parent[b] = a;
    heavy[a] = h[heavy[a]] > h[heavy[b]] ? heavy[a] : heavy[b];
  }
}

int anc[NMAX+1][LOGMAX+1];
int dep[NMAX+1];
void dfs( int node, int par = 0 ) {
  int i;
  anc[node][0] = par;
  dep[node] = dep[par] + 1;
  for( i = 1; i < LOGMAX; i++ ) {
    if( anc[node][i-1] != 0 )
      anc[node][i] = anc[anc[node][i-1]][i-1];
  }
  for( auto vec: edges[node] ) {
    if( vec != par )
      dfs( vec, node );
  }
}
int dist( int a, int b ) {
  int ca = a, cb = b, i;
  if( dep[a] < dep[b] )
    swap( a, b );
  int d = dep[a] - dep[b];
  for( i = 0; i < LOGMAX; i++ ) {
    if( d & ( 1 << i ) )
      a = anc[a][i];
  }
  for( i = LOGMAX - 1; i >= 0; i-- ) {
    if( anc[a][i] != anc[b][i] )
      a = anc[a][i], b = anc[b][i];
  }
  if( a != b )
    a = anc[a][0], b = anc[b][0];
  return dep[ca] - dep[a] + dep[cb] - dep[a];
}

int dp[NMAX+1], ord[NMAX+1];
void solve() {
  int n, i, a, b, nxt;
  cin >> n;
  for( i = 1; i <= n; i++ ) {
    cin >> h[i].first, h[i].second = i;
    ord[i] = i;
  }
  for( i = 0; i < n - 1; i++ ) {
    cin >> a >> b;
    edges[a].push_back( b );
    edges[b].push_back( a );
  }
  sort( ord + 1, ord + n + 1, []( int a, int b ) {
      return h[a] < h[b];
  } );
  for( i = 1; i <= n; i++ )
    parent[i] = i, heavy[i] = i;
  dfs( 1 );
  //cout << dist( 3, 5 ) << "\n";
  for( i = 1; i <= n; i++ ) {
    for( auto vec: edges[ord[i]] ) {
      if( h[vec] < h[ord[i]] ) {
        nxt = heavy[find(vec)];
        dp[ord[i]] = max( dp[ord[i]], dp[nxt] + dist( nxt, ord[i] ) );
      }
    }
    for( auto vec: edges[ord[i]] ) {
      if( h[vec] < h[ord[i]] )
        unite( vec, ord[i] );
    }
  }
  cout << dp[ord[n]];
}
int main() {
  ios_base::sync_with_stdio( false );
  cin.tie( NULL );
  cout.tie( NULL );
  int t = 1;
  //cin >> t;
  while( t-- ) {
    solve();
  }
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21596 KB Output is correct
2 Correct 5 ms 21664 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 4 ms 21688 KB Output is correct
5 Correct 4 ms 21596 KB Output is correct
6 Correct 4 ms 21672 KB Output is correct
7 Correct 4 ms 21700 KB Output is correct
8 Correct 4 ms 21684 KB Output is correct
9 Correct 4 ms 21916 KB Output is correct
10 Correct 4 ms 21596 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21596 KB Output is correct
2 Correct 5 ms 21664 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 4 ms 21688 KB Output is correct
5 Correct 4 ms 21596 KB Output is correct
6 Correct 4 ms 21672 KB Output is correct
7 Correct 4 ms 21700 KB Output is correct
8 Correct 4 ms 21684 KB Output is correct
9 Correct 4 ms 21916 KB Output is correct
10 Correct 4 ms 21596 KB Output is correct
11 Correct 6 ms 21596 KB Output is correct
12 Correct 4 ms 21596 KB Output is correct
13 Correct 5 ms 21596 KB Output is correct
14 Correct 4 ms 21596 KB Output is correct
15 Correct 4 ms 21596 KB Output is correct
16 Correct 4 ms 21608 KB Output is correct
17 Correct 5 ms 21684 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21596 KB Output is correct
2 Correct 5 ms 21664 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 4 ms 21688 KB Output is correct
5 Correct 4 ms 21596 KB Output is correct
6 Correct 4 ms 21672 KB Output is correct
7 Correct 4 ms 21700 KB Output is correct
8 Correct 4 ms 21684 KB Output is correct
9 Correct 4 ms 21916 KB Output is correct
10 Correct 4 ms 21596 KB Output is correct
11 Correct 6 ms 21596 KB Output is correct
12 Correct 4 ms 21596 KB Output is correct
13 Correct 5 ms 21596 KB Output is correct
14 Correct 4 ms 21596 KB Output is correct
15 Correct 4 ms 21596 KB Output is correct
16 Correct 4 ms 21608 KB Output is correct
17 Correct 5 ms 21684 KB Output is correct
18 Correct 7 ms 22108 KB Output is correct
19 Correct 7 ms 22188 KB Output is correct
20 Correct 8 ms 22108 KB Output is correct
21 Correct 8 ms 22108 KB Output is correct
22 Correct 7 ms 22108 KB Output is correct
23 Correct 7 ms 22108 KB Output is correct
24 Correct 7 ms 22108 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21596 KB Output is correct
2 Correct 5 ms 21664 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 4 ms 21688 KB Output is correct
5 Correct 4 ms 21596 KB Output is correct
6 Correct 4 ms 21672 KB Output is correct
7 Correct 4 ms 21700 KB Output is correct
8 Correct 4 ms 21684 KB Output is correct
9 Correct 4 ms 21916 KB Output is correct
10 Correct 4 ms 21596 KB Output is correct
11 Correct 6 ms 21596 KB Output is correct
12 Correct 4 ms 21596 KB Output is correct
13 Correct 5 ms 21596 KB Output is correct
14 Correct 4 ms 21596 KB Output is correct
15 Correct 4 ms 21596 KB Output is correct
16 Correct 4 ms 21608 KB Output is correct
17 Correct 5 ms 21684 KB Output is correct
18 Correct 7 ms 22108 KB Output is correct
19 Correct 7 ms 22188 KB Output is correct
20 Correct 8 ms 22108 KB Output is correct
21 Correct 8 ms 22108 KB Output is correct
22 Correct 7 ms 22108 KB Output is correct
23 Correct 7 ms 22108 KB Output is correct
24 Correct 7 ms 22108 KB Output is correct
25 Correct 4 ms 21592 KB Output is correct
26 Correct 7 ms 21876 KB Output is correct
27 Correct 7 ms 22104 KB Output is correct
28 Correct 7 ms 21852 KB Output is correct
29 Correct 7 ms 22012 KB Output is correct
30 Correct 8 ms 21848 KB Output is correct
31 Correct 7 ms 22048 KB Output is correct
32 Correct 7 ms 21852 KB Output is correct
33 Correct 7 ms 21992 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21596 KB Output is correct
2 Correct 5 ms 21664 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 4 ms 21688 KB Output is correct
5 Correct 4 ms 21596 KB Output is correct
6 Correct 4 ms 21672 KB Output is correct
7 Correct 4 ms 21700 KB Output is correct
8 Correct 4 ms 21684 KB Output is correct
9 Correct 4 ms 21916 KB Output is correct
10 Correct 4 ms 21596 KB Output is correct
11 Correct 6 ms 21596 KB Output is correct
12 Correct 4 ms 21596 KB Output is correct
13 Correct 5 ms 21596 KB Output is correct
14 Correct 4 ms 21596 KB Output is correct
15 Correct 4 ms 21596 KB Output is correct
16 Correct 4 ms 21608 KB Output is correct
17 Correct 5 ms 21684 KB Output is correct
18 Correct 7 ms 22108 KB Output is correct
19 Correct 7 ms 22188 KB Output is correct
20 Correct 8 ms 22108 KB Output is correct
21 Correct 8 ms 22108 KB Output is correct
22 Correct 7 ms 22108 KB Output is correct
23 Correct 7 ms 22108 KB Output is correct
24 Correct 7 ms 22108 KB Output is correct
25 Incorrect 127 ms 64516 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21596 KB Output is correct
2 Correct 4 ms 21596 KB Output is correct
3 Correct 181 ms 53224 KB Output is correct
4 Correct 180 ms 53060 KB Output is correct
5 Correct 186 ms 53076 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21596 KB Output is correct
2 Correct 5 ms 21664 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 4 ms 21688 KB Output is correct
5 Correct 4 ms 21596 KB Output is correct
6 Correct 4 ms 21672 KB Output is correct
7 Correct 4 ms 21700 KB Output is correct
8 Correct 4 ms 21684 KB Output is correct
9 Correct 4 ms 21916 KB Output is correct
10 Correct 4 ms 21596 KB Output is correct
11 Correct 6 ms 21596 KB Output is correct
12 Correct 4 ms 21596 KB Output is correct
13 Correct 5 ms 21596 KB Output is correct
14 Correct 4 ms 21596 KB Output is correct
15 Correct 4 ms 21596 KB Output is correct
16 Correct 4 ms 21608 KB Output is correct
17 Correct 5 ms 21684 KB Output is correct
18 Correct 7 ms 22108 KB Output is correct
19 Correct 7 ms 22188 KB Output is correct
20 Correct 8 ms 22108 KB Output is correct
21 Correct 8 ms 22108 KB Output is correct
22 Correct 7 ms 22108 KB Output is correct
23 Correct 7 ms 22108 KB Output is correct
24 Correct 7 ms 22108 KB Output is correct
25 Correct 4 ms 21592 KB Output is correct
26 Correct 7 ms 21876 KB Output is correct
27 Correct 7 ms 22104 KB Output is correct
28 Correct 7 ms 21852 KB Output is correct
29 Correct 7 ms 22012 KB Output is correct
30 Correct 8 ms 21848 KB Output is correct
31 Correct 7 ms 22048 KB Output is correct
32 Correct 7 ms 21852 KB Output is correct
33 Correct 7 ms 21992 KB Output is correct
34 Incorrect 127 ms 64516 KB Output isn't correct
35 Halted 0 ms 0 KB -