Submission #1116898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116898		ntdaccode	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	2070 ms	61004 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> ii;

const int M=2e5+10;

int n,p[M];
vector<int> ke[M];
int num[M],tail[M],cnt = 0,up[M][20],d[M];
int arr[M];
int test = 0;
void dfs(int u,int p)
{
   test ++;
   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];
void solve(int u)
{
   upd(1,1,n,num[u],tail[u],-1e6);

   int 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[u],tail[u],1e6);
   upd(1,1,n,1,n,-1e6);

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

      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],-1e6);
   }
   upd(1,1,n,1,n,1e6);
}

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].push_back(v);
      ke[v].push_back(u);
  }
  up[1][0]  = 1;
  dfs(1,0);
  build(1,1,n);
  int x = t[1].second;
  solve(x);
  cout << f[x];

}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:122:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     freopen("1.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:123:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:128:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:129:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 23 / 23
• Subtask 7: 0 / 26