Submission #1116926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116926		ntdaccode	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	2062 ms	108872 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> ii;

const int M=4e5+10;

int n,p[M];
vector<int> ke[M];
int num[M],tail[M],cnt = 0,d[M],par[M];
ii rmq[M][20];
int lg[M],pos[M],id = 0;
int arr[M];
void dfs(int u,int p)
{
   num[u] = ++ cnt;
   arr[cnt] = u;
   pos[u] = ++id;
  rmq[id][0] = {d[u], u};
   for(int v : ke[u]) {
      if(v == p) continue;
      d[v] = d[u] + 1;
      par[v] = u;
      dfs(v,u);
      rmq[++id][0] = {d[u], 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){
  int l = pos[u], r = pos[v];
  if(l > r) swap(l, r);
  int k = lg[r - l + 1];
  return min(rmq[l][k], rmq[r-(1<<k)+1][k]).second;
}

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 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 == par[u]) 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);
  }
  dfs(1,0);
   for(int j = 1; j <= 20; j++)
    for(int i = 1; i + (1 << j) - 1 <= id; i++)
      rmq[i][j] = min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);

  for(int i = 2; i <= id; i++) lg[i] = lg[i >> 1] + 1;
  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: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.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:124:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |     freopen("1.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
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".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:130:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |     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