oj.uz

Submission #1116898

# Submission time Handle Problem Language Result Execution time Memory
1116898 2024-11-22T14:23:43 Z ntdaccode Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 2000 ms 61004 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12624 KB Output is correct
2 Correct 3 ms 12624 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 ms 12624 KB Output is correct
8 Correct 2 ms 12624 KB Output is correct
9 Correct 3 ms 14672 KB Output is correct
10 Correct 2 ms 12624 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12624 KB Output is correct
2 Correct 3 ms 12624 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 ms 12624 KB Output is correct
8 Correct 2 ms 12624 KB Output is correct
9 Correct 3 ms 14672 KB Output is correct
10 Correct 2 ms 12624 KB Output is correct
11 Correct 3 ms 14672 KB Output is correct
12 Correct 3 ms 12624 KB Output is correct
13 Correct 3 ms 12624 KB Output is correct
14 Correct 3 ms 12624 KB Output is correct
15 Correct 3 ms 12624 KB Output is correct
16 Correct 3 ms 12624 KB Output is correct
17 Correct 3 ms 12880 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12624 KB Output is correct
2 Correct 3 ms 12624 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 ms 12624 KB Output is correct
8 Correct 2 ms 12624 KB Output is correct
9 Correct 3 ms 14672 KB Output is correct
10 Correct 2 ms 12624 KB Output is correct
11 Correct 3 ms 14672 KB Output is correct
12 Correct 3 ms 12624 KB Output is correct
13 Correct 3 ms 12624 KB Output is correct
14 Correct 3 ms 12624 KB Output is correct
15 Correct 3 ms 12624 KB Output is correct
16 Correct 3 ms 12624 KB Output is correct
17 Correct 3 ms 12880 KB Output is correct
18 Correct 7 ms 15400 KB Output is correct
19 Correct 7 ms 13560 KB Output is correct
20 Correct 8 ms 13392 KB Output is correct
21 Correct 6 ms 13392 KB Output is correct
22 Correct 7 ms 13392 KB Output is correct
23 Correct 9 ms 13500 KB Output is correct
24 Correct 8 ms 13392 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12624 KB Output is correct
2 Correct 3 ms 12624 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 ms 12624 KB Output is correct
8 Correct 2 ms 12624 KB Output is correct
9 Correct 3 ms 14672 KB Output is correct
10 Correct 2 ms 12624 KB Output is correct
11 Correct 3 ms 14672 KB Output is correct
12 Correct 3 ms 12624 KB Output is correct
13 Correct 3 ms 12624 KB Output is correct
14 Correct 3 ms 12624 KB Output is correct
15 Correct 3 ms 12624 KB Output is correct
16 Correct 3 ms 12624 KB Output is correct
17 Correct 3 ms 12880 KB Output is correct
18 Correct 7 ms 15400 KB Output is correct
19 Correct 7 ms 13560 KB Output is correct
20 Correct 8 ms 13392 KB Output is correct
21 Correct 6 ms 13392 KB Output is correct
22 Correct 7 ms 13392 KB Output is correct
23 Correct 9 ms 13500 KB Output is correct
24 Correct 8 ms 13392 KB Output is correct
25 Correct 3 ms 12624 KB Output is correct
26 Correct 9 ms 13564 KB Output is correct
27 Correct 8 ms 13368 KB Output is correct
28 Correct 11 ms 13256 KB Output is correct
29 Correct 8 ms 13392 KB Output is correct
30 Correct 8 ms 13136 KB Output is correct
31 Correct 7 ms 13044 KB Output is correct
32 Correct 8 ms 13136 KB Output is correct
33 Correct 8 ms 13136 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12624 KB Output is correct
2 Correct 3 ms 12624 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 ms 12624 KB Output is correct
8 Correct 2 ms 12624 KB Output is correct
9 Correct 3 ms 14672 KB Output is correct
10 Correct 2 ms 12624 KB Output is correct
11 Correct 3 ms 14672 KB Output is correct
12 Correct 3 ms 12624 KB Output is correct
13 Correct 3 ms 12624 KB Output is correct
14 Correct 3 ms 12624 KB Output is correct
15 Correct 3 ms 12624 KB Output is correct
16 Correct 3 ms 12624 KB Output is correct
17 Correct 3 ms 12880 KB Output is correct
18 Correct 7 ms 15400 KB Output is correct
19 Correct 7 ms 13560 KB Output is correct
20 Correct 8 ms 13392 KB Output is correct
21 Correct 6 ms 13392 KB Output is correct
22 Correct 7 ms 13392 KB Output is correct
23 Correct 9 ms 13500 KB Output is correct
24 Correct 8 ms 13392 KB Output is correct
25 Execution timed out 2070 ms 61004 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12624 KB Output is correct
2 Correct 3 ms 12624 KB Output is correct
3 Correct 249 ms 46056 KB Output is correct
4 Correct 235 ms 45652 KB Output is correct
5 Correct 237 ms 45384 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12624 KB Output is correct
2 Correct 3 ms 12624 KB Output is correct
3 Correct 3 ms 12624 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 3 ms 12624 KB Output is correct
8 Correct 2 ms 12624 KB Output is correct
9 Correct 3 ms 14672 KB Output is correct
10 Correct 2 ms 12624 KB Output is correct
11 Correct 3 ms 14672 KB Output is correct
12 Correct 3 ms 12624 KB Output is correct
13 Correct 3 ms 12624 KB Output is correct
14 Correct 3 ms 12624 KB Output is correct
15 Correct 3 ms 12624 KB Output is correct
16 Correct 3 ms 12624 KB Output is correct
17 Correct 3 ms 12880 KB Output is correct
18 Correct 7 ms 15400 KB Output is correct
19 Correct 7 ms 13560 KB Output is correct
20 Correct 8 ms 13392 KB Output is correct
21 Correct 6 ms 13392 KB Output is correct
22 Correct 7 ms 13392 KB Output is correct
23 Correct 9 ms 13500 KB Output is correct
24 Correct 8 ms 13392 KB Output is correct
25 Correct 3 ms 12624 KB Output is correct
26 Correct 9 ms 13564 KB Output is correct
27 Correct 8 ms 13368 KB Output is correct
28 Correct 11 ms 13256 KB Output is correct
29 Correct 8 ms 13392 KB Output is correct
30 Correct 8 ms 13136 KB Output is correct
31 Correct 7 ms 13044 KB Output is correct
32 Correct 8 ms 13136 KB Output is correct
33 Correct 8 ms 13136 KB Output is correct
34 Execution timed out 2070 ms 61004 KB Time limit exceeded
35 Halted 0 ms 0 KB -