oj.uz

Submission #1116926

# Submission time Handle Problem Language Result Execution time Memory
1116926 2024-11-22T15:19:02 Z ntdaccode Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 2000 ms 108872 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20816 KB Output is correct
2 Correct 4 ms 20816 KB Output is correct
3 Correct 4 ms 20988 KB Output is correct
4 Correct 4 ms 22864 KB Output is correct
5 Correct 4 ms 21028 KB Output is correct
6 Correct 5 ms 22864 KB Output is correct
7 Correct 4 ms 20816 KB Output is correct
8 Correct 4 ms 20816 KB Output is correct
9 Correct 4 ms 22864 KB Output is correct
10 Correct 4 ms 20816 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20816 KB Output is correct
2 Correct 4 ms 20816 KB Output is correct
3 Correct 4 ms 20988 KB Output is correct
4 Correct 4 ms 22864 KB Output is correct
5 Correct 4 ms 21028 KB Output is correct
6 Correct 5 ms 22864 KB Output is correct
7 Correct 4 ms 20816 KB Output is correct
8 Correct 4 ms 20816 KB Output is correct
9 Correct 4 ms 22864 KB Output is correct
10 Correct 4 ms 20816 KB Output is correct
11 Correct 4 ms 22864 KB Output is correct
12 Correct 3 ms 20816 KB Output is correct
13 Correct 4 ms 20832 KB Output is correct
14 Correct 4 ms 20816 KB Output is correct
15 Correct 4 ms 20816 KB Output is correct
16 Correct 4 ms 20984 KB Output is correct
17 Correct 4 ms 21244 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20816 KB Output is correct
2 Correct 4 ms 20816 KB Output is correct
3 Correct 4 ms 20988 KB Output is correct
4 Correct 4 ms 22864 KB Output is correct
5 Correct 4 ms 21028 KB Output is correct
6 Correct 5 ms 22864 KB Output is correct
7 Correct 4 ms 20816 KB Output is correct
8 Correct 4 ms 20816 KB Output is correct
9 Correct 4 ms 22864 KB Output is correct
10 Correct 4 ms 20816 KB Output is correct
11 Correct 4 ms 22864 KB Output is correct
12 Correct 3 ms 20816 KB Output is correct
13 Correct 4 ms 20832 KB Output is correct
14 Correct 4 ms 20816 KB Output is correct
15 Correct 4 ms 20816 KB Output is correct
16 Correct 4 ms 20984 KB Output is correct
17 Correct 4 ms 21244 KB Output is correct
18 Correct 8 ms 23632 KB Output is correct
19 Correct 8 ms 21584 KB Output is correct
20 Correct 7 ms 21584 KB Output is correct
21 Correct 7 ms 21584 KB Output is correct
22 Correct 8 ms 21584 KB Output is correct
23 Correct 7 ms 21584 KB Output is correct
24 Correct 7 ms 19792 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20816 KB Output is correct
2 Correct 4 ms 20816 KB Output is correct
3 Correct 4 ms 20988 KB Output is correct
4 Correct 4 ms 22864 KB Output is correct
5 Correct 4 ms 21028 KB Output is correct
6 Correct 5 ms 22864 KB Output is correct
7 Correct 4 ms 20816 KB Output is correct
8 Correct 4 ms 20816 KB Output is correct
9 Correct 4 ms 22864 KB Output is correct
10 Correct 4 ms 20816 KB Output is correct
11 Correct 4 ms 22864 KB Output is correct
12 Correct 3 ms 20816 KB Output is correct
13 Correct 4 ms 20832 KB Output is correct
14 Correct 4 ms 20816 KB Output is correct
15 Correct 4 ms 20816 KB Output is correct
16 Correct 4 ms 20984 KB Output is correct
17 Correct 4 ms 21244 KB Output is correct
18 Correct 8 ms 23632 KB Output is correct
19 Correct 8 ms 21584 KB Output is correct
20 Correct 7 ms 21584 KB Output is correct
21 Correct 7 ms 21584 KB Output is correct
22 Correct 8 ms 21584 KB Output is correct
23 Correct 7 ms 21584 KB Output is correct
24 Correct 7 ms 19792 KB Output is correct
25 Correct 3 ms 18768 KB Output is correct
26 Correct 8 ms 19536 KB Output is correct
27 Correct 9 ms 19536 KB Output is correct
28 Correct 9 ms 21584 KB Output is correct
29 Correct 9 ms 21584 KB Output is correct
30 Correct 8 ms 21328 KB Output is correct
31 Correct 8 ms 21416 KB Output is correct
32 Correct 8 ms 21328 KB Output is correct
33 Correct 8 ms 21328 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20816 KB Output is correct
2 Correct 4 ms 20816 KB Output is correct
3 Correct 4 ms 20988 KB Output is correct
4 Correct 4 ms 22864 KB Output is correct
5 Correct 4 ms 21028 KB Output is correct
6 Correct 5 ms 22864 KB Output is correct
7 Correct 4 ms 20816 KB Output is correct
8 Correct 4 ms 20816 KB Output is correct
9 Correct 4 ms 22864 KB Output is correct
10 Correct 4 ms 20816 KB Output is correct
11 Correct 4 ms 22864 KB Output is correct
12 Correct 3 ms 20816 KB Output is correct
13 Correct 4 ms 20832 KB Output is correct
14 Correct 4 ms 20816 KB Output is correct
15 Correct 4 ms 20816 KB Output is correct
16 Correct 4 ms 20984 KB Output is correct
17 Correct 4 ms 21244 KB Output is correct
18 Correct 8 ms 23632 KB Output is correct
19 Correct 8 ms 21584 KB Output is correct
20 Correct 7 ms 21584 KB Output is correct
21 Correct 7 ms 21584 KB Output is correct
22 Correct 8 ms 21584 KB Output is correct
23 Correct 7 ms 21584 KB Output is correct
24 Correct 7 ms 19792 KB Output is correct
25 Execution timed out 2062 ms 108872 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20816 KB Output is correct
2 Correct 4 ms 20816 KB Output is correct
3 Correct 312 ms 99168 KB Output is correct
4 Correct 309 ms 99412 KB Output is correct
5 Correct 293 ms 98928 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20816 KB Output is correct
2 Correct 4 ms 20816 KB Output is correct
3 Correct 4 ms 20988 KB Output is correct
4 Correct 4 ms 22864 KB Output is correct
5 Correct 4 ms 21028 KB Output is correct
6 Correct 5 ms 22864 KB Output is correct
7 Correct 4 ms 20816 KB Output is correct
8 Correct 4 ms 20816 KB Output is correct
9 Correct 4 ms 22864 KB Output is correct
10 Correct 4 ms 20816 KB Output is correct
11 Correct 4 ms 22864 KB Output is correct
12 Correct 3 ms 20816 KB Output is correct
13 Correct 4 ms 20832 KB Output is correct
14 Correct 4 ms 20816 KB Output is correct
15 Correct 4 ms 20816 KB Output is correct
16 Correct 4 ms 20984 KB Output is correct
17 Correct 4 ms 21244 KB Output is correct
18 Correct 8 ms 23632 KB Output is correct
19 Correct 8 ms 21584 KB Output is correct
20 Correct 7 ms 21584 KB Output is correct
21 Correct 7 ms 21584 KB Output is correct
22 Correct 8 ms 21584 KB Output is correct
23 Correct 7 ms 21584 KB Output is correct
24 Correct 7 ms 19792 KB Output is correct
25 Correct 3 ms 18768 KB Output is correct
26 Correct 8 ms 19536 KB Output is correct
27 Correct 9 ms 19536 KB Output is correct
28 Correct 9 ms 21584 KB Output is correct
29 Correct 9 ms 21584 KB Output is correct
30 Correct 8 ms 21328 KB Output is correct
31 Correct 8 ms 21416 KB Output is correct
32 Correct 8 ms 21328 KB Output is correct
33 Correct 8 ms 21328 KB Output is correct
34 Execution timed out 2062 ms 108872 KB Time limit exceeded
35 Halted 0 ms 0 KB -