oj.uz

Submission #1116872

# Submission time Handle Problem Language Result Execution time Memory
1116872 2024-11-22T13:53:07 Z ntdaccode Cat Exercise (JOI23_ho_t4) C++17
0 / 100
 2000 ms 1048576 KB 
#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back

using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M=1e6+10;
const int N=1e3+10;
const int mod=1e9+7;

int n,p[M];
vector<int> ke[M];
int num[M],tail[M],cnt = 0,up[M][20],d[M];
int arr[M];
void dfs(int u,int p)
{
   num[u] = ++ cnt;
   arr[cnt] = u;
   for(int i = 1;i <= 18; i++) up[u][i] = up[up[u][i - 1]][i - 1];
   for(int v : ke[u]) {
      if(v == p) continue;
      d[v] = d[u] + 1;
      up[v][0] = u;
      dfs(v,u);
   }
   tail[u] = cnt;
}

bool anc(int u ,int v)
{
   return num[u] <= num[v] && tail[u] >= tail[v];
}

int lca(int u,int v)
{
   if(anc(u,v)) return u;
   if(anc(v,u)) return v;
   for(int i = 18;i >= 0;i--) if(!anc(up[u][i],v)) u = up[u][i];
   return up[u][0];
}

int dist(int u,int v)
{
   int x = lca(u,v);
   return d[u] + d[v] - 2 * d[x];
}


ii t[4 * M];
int lz[4 * M];
void lazy(int s)
{
   t[s * 2].first += lz[s];
   t[s * 2 + 1].first += lz[s];
   lz[s * 2] += lz[s];
   lz[s * 2 + 1] += lz[s];
   lz[s] = 0;
   return ;
}
void build(int s,int l,int r)
{
   if(l == r) {
      t[s] = {p[arr[l]],arr[l]};
      return ;
   }
   int mid = (l + r)/2;
   build(s * 2,l,mid);
   build(s * 2 + 1,mid + 1,r);
   t[s] = max(t[s * 2], t[s * 2 + 1]);
}

void upd(int s,int l,int r,int u,int v,int val)
{
   if(v < l || r < u) return ;
   if(u <= l && r <= v) {
      t[s].first += val;
      lz[s] += val;
      return ;
   }
   int mid = (l + r)/2;
   if(l != r && lz[s]) lazy(s);
   upd(s * 2,l,mid,u,v,val);
   upd(s * 2 + 1,mid + 1,r,u,v,val);
   t[s] = max(t[s * 2],t[s * 2 + 1]);
}
int pos[M],f[M];
int solve(int u)
{
   upd(1,1,n,num[u],tail[u],-1e9);

   int nxt = t[1].second;
  // cout << u <<  ' ' << t[1].first << " " << t[1].second <<   "\n";
   if(t[1].first > 0) {
   solve(nxt);
   f[u] = max(f[u],f[nxt] + dist(u,nxt));
   }

   upd(1,1,n,num[u],tail[u],1e9);
   upd(1,1,n,1,n,-1e9);

   for(int v : ke[u]) {
         if(v == up[u][0]) continue;
      upd(1,1,n,num[v],tail[v],1e9);

      nxt = t[1].second;
      if(t[1].first > 0) {
         solve(nxt);
         f[u] = max(f[u],f[nxt] + dist(u,nxt));
      }

      upd(1,1,n,num[v],tail[v],-1e9);
   }
   upd(1,1,n,1,n,1e9);
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  if(fopen("1.inp","r"))
  {
    freopen("1.inp","r",stdin);
    freopen("1.out","w",stdout);
  }
  #define task ""
  if(fopen(task".inp","r"))
  {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

  cin >> n ;
  for(int i =1;i <= n; i++) cin >> p[i];
  for(int i =1;i <= n - 1; i++) {
      int u,v;
      cin >> u >> v;
      ke[u].pb(v);
      ke[v].pb(u);
  }
  up[1][0]  = 1;
  dfs(1,0);
  build(1,1,n);
  int x = t[1].second;
  solve(x);
  cout << f[x];

}

Compilation message

Main.cpp: In function 'long long int solve(long long int)':
Main.cpp:116:1: warning: no return statement in function returning non-void [-Wreturn-type]
  116 | }
      | ^
Main.cpp: In function 'int32_t main()':
Main.cpp:125:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:131:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:132:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1737 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -