oj.uz

Submission #492981

# Submission time Handle Problem Language Result Execution time Memory
492981 2021-12-09T21:39:43 Z ivan_tudor Cats or Dogs (JOI18_catdog) C++14
100 / 100
 477 ms 58544 KB 
#include "catdog.h"
#include<assert.h>
using namespace std;
const int N = 500005;
const int INF = 1e9;
int n;
int scores[2][N];
int curl[2][N];
struct SegmentTree{
  int ans[2][2];
  SegmentTree(){
    for(int i =0; i< 2; i++){
      for(int j = 0; j < 2; j++)
        ans[i][j] = INF;
    }
  }
};
SegmentTree NIL;
SegmentTree join(SegmentTree a, SegmentTree b){
  SegmentTree rsp;
  for(int i = 0; i <= 1; i++){
    for(int j = 0; j <= 1; j++){
      for(int midl = 0; midl <=1 ;midl++){
        for(int midr = 0; midr <=1; midr++){
          rsp.ans[i][j] = min(rsp.ans[i][j], a.ans[i][midl] + b.ans[midr][j] + (midl!=midr));
        }
      }
    }
  }
  return rsp;
}
SegmentTree build(int nod, int animal){
  SegmentTree rsp;
  for(int i =0; i <= 1; i++){
    if(animal == i || animal == 2)
      rsp.ans[i][i] = 0;
    rsp.ans[i][i] += scores[i][nod];
  }
  return rsp;
}
SegmentTree aint[4*N];
int getminscore(SegmentTree chain, int pet){
  int ans = INF;
  for(int i = 0; i <= 1; i++){
    ans = min(ans, chain.ans[pet][i]);
    ans = min(ans, chain.ans[pet^1][i] + 1);
  }
  return ans;
}
void update(int nod, int l, int r, int upoz, int utype){
  if(l > upoz || r < upoz)
    return;
  if(l == r){
    aint[nod] = build(upoz, utype);
    return;
  }
  int mid = (l + r)/2;
  update(2*nod, l, mid, upoz, utype);
  update(2*nod + 1, mid +1, r, upoz, utype);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
}
SegmentTree query(int nod, int l, int r, int ql, int qr){
  if(ql <= l && r <= qr)
    return aint[nod];
  int mid = (l + r)/2;
  SegmentTree rsp;
  if(ql <= mid && mid < qr)
    rsp = join(query(2*nod, l, mid, ql, qr), query(2*nod + 1, mid + 1, r, ql, qr));
  else if(qr <= mid)
    rsp = query(2*nod, l, mid, ql, qr);
  else if(ql > mid)
    rsp = query(2*nod + 1, mid + 1, r, ql, qr);
  else
    assert(0);
  return rsp;
}

vector<int> gr[N];
int par[N];
int sz[N];
int id[N];
int head[N];
int low[N];
int tp[N];
void dfs_init(int nod, int dad){
  par[nod] = dad;
  sz[nod] = 1;
  for(auto x:gr[nod]){
    if(x == dad)
      continue;
    dfs_init(x, nod);
    sz[nod] += sz[x];
  }
}
void dfs_heavy(int nod, int dad,int &idd, int chead){
  head[nod] = chead;
  low[chead] = nod;
  id[nod] = idd++;
  int mson = -1;
  for(auto x:gr[nod]){
    if(x == dad)
      continue;
    if(mson == -1 || sz[x] > sz[mson])
      mson = x;
  }
  if(mson == -1)
    return;
  dfs_heavy(mson, nod, idd, chead);
  for(auto x:gr[nod]){
    if(x == dad || x == mson)
      continue;
    dfs_heavy(x, nod, idd, x);
  }
}
SegmentTree update_heavy(int nod, int type){
  tp[nod] = type;
  int hd = head[nod];
  update(1, 1, n, id[nod], type);
  SegmentTree chain = query(1, 1, n, id[hd], id[low[hd]]);
  if(hd == 1)
    return chain;
  for(int i = 0; i<=1; i++){
    scores[i][id[par[hd]]] -= curl[i][id[hd]];
    curl[i][id[hd]] = getminscore(chain, i);
    scores[i][id[par[hd]]] += curl[i][id[hd]];
  }
  return update_heavy(par[hd], tp[par[hd]]);
}

void build_aint(int nod, int l, int r){
  if(l == r){
    aint[nod] = build(nod, tp[l]);
    return;
  }
  int mid = (l + r)/2;
  build_aint(2*nod, l, mid);
  build_aint(2*nod + 1, mid + 1, r);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
}

void initialize(int N, std::vector<int> A, std::vector<int> B){
  NIL = build(0, 2);
  n = N;
  for(int i = 0; i < N - 1; i++){
    gr[A[i]].push_back(B[i]);
    gr[B[i]].push_back(A[i]);
  }
  for(int i = 1; i<=n; i++)
    tp[i] = 2;
  build_aint(1,  1,  n);
  dfs_init(1, 0);
  int cnt = 1;
  dfs_heavy(1, 0, cnt, 1);
};
int cat(int v){
  SegmentTree rsp = update_heavy(v, 0);
  return min(getminscore(rsp, 0), getminscore(rsp, 1));
}
int dog(int v){
  SegmentTree rsp = update_heavy(v, 1);
  return min(getminscore(rsp, 0), getminscore(rsp, 1));
}
int neighbor(int v){
  SegmentTree rsp = update_heavy(v, 2);
  return min(getminscore(rsp, 0), getminscore(rsp, 1));
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 43340 KB Output is correct
2 Correct 20 ms 43320 KB Output is correct
3 Correct 20 ms 43340 KB Output is correct
4 Correct 20 ms 43404 KB Output is correct
5 Correct 21 ms 43340 KB Output is correct
6 Correct 21 ms 43320 KB Output is correct
7 Correct 20 ms 43372 KB Output is correct
8 Correct 20 ms 43404 KB Output is correct
9 Correct 20 ms 43380 KB Output is correct
10 Correct 20 ms 43340 KB Output is correct
11 Correct 20 ms 43468 KB Output is correct
12 Correct 19 ms 43380 KB Output is correct
13 Correct 20 ms 43340 KB Output is correct
14 Correct 20 ms 43340 KB Output is correct
15 Correct 20 ms 43340 KB Output is correct
16 Correct 20 ms 43408 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 43340 KB Output is correct
2 Correct 20 ms 43320 KB Output is correct
3 Correct 20 ms 43340 KB Output is correct
4 Correct 20 ms 43404 KB Output is correct
5 Correct 21 ms 43340 KB Output is correct
6 Correct 21 ms 43320 KB Output is correct
7 Correct 20 ms 43372 KB Output is correct
8 Correct 20 ms 43404 KB Output is correct
9 Correct 20 ms 43380 KB Output is correct
10 Correct 20 ms 43340 KB Output is correct
11 Correct 20 ms 43468 KB Output is correct
12 Correct 19 ms 43380 KB Output is correct
13 Correct 20 ms 43340 KB Output is correct
14 Correct 20 ms 43340 KB Output is correct
15 Correct 20 ms 43340 KB Output is correct
16 Correct 20 ms 43408 KB Output is correct
17 Correct 26 ms 43448 KB Output is correct
18 Correct 20 ms 43488 KB Output is correct
19 Correct 21 ms 43396 KB Output is correct
20 Correct 22 ms 43356 KB Output is correct
21 Correct 22 ms 43324 KB Output is correct
22 Correct 21 ms 43328 KB Output is correct
23 Correct 23 ms 43456 KB Output is correct
24 Correct 22 ms 43464 KB Output is correct
25 Correct 24 ms 43392 KB Output is correct
26 Correct 21 ms 43332 KB Output is correct
27 Correct 21 ms 43428 KB Output is correct
28 Correct 22 ms 43500 KB Output is correct
29 Correct 20 ms 43472 KB Output is correct
30 Correct 20 ms 43340 KB Output is correct
31 Correct 20 ms 43472 KB Output is correct
32 Correct 20 ms 43380 KB Output is correct

Subtask #3
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 43340 KB Output is correct
2 Correct 20 ms 43320 KB Output is correct
3 Correct 20 ms 43340 KB Output is correct
4 Correct 20 ms 43404 KB Output is correct
5 Correct 21 ms 43340 KB Output is correct
6 Correct 21 ms 43320 KB Output is correct
7 Correct 20 ms 43372 KB Output is correct
8 Correct 20 ms 43404 KB Output is correct
9 Correct 20 ms 43380 KB Output is correct
10 Correct 20 ms 43340 KB Output is correct
11 Correct 20 ms 43468 KB Output is correct
12 Correct 19 ms 43380 KB Output is correct
13 Correct 20 ms 43340 KB Output is correct
14 Correct 20 ms 43340 KB Output is correct
15 Correct 20 ms 43340 KB Output is correct
16 Correct 20 ms 43408 KB Output is correct
17 Correct 26 ms 43448 KB Output is correct
18 Correct 20 ms 43488 KB Output is correct
19 Correct 21 ms 43396 KB Output is correct
20 Correct 22 ms 43356 KB Output is correct
21 Correct 22 ms 43324 KB Output is correct
22 Correct 21 ms 43328 KB Output is correct
23 Correct 23 ms 43456 KB Output is correct
24 Correct 22 ms 43464 KB Output is correct
25 Correct 24 ms 43392 KB Output is correct
26 Correct 21 ms 43332 KB Output is correct
27 Correct 21 ms 43428 KB Output is correct
28 Correct 22 ms 43500 KB Output is correct
29 Correct 20 ms 43472 KB Output is correct
30 Correct 20 ms 43340 KB Output is correct
31 Correct 20 ms 43472 KB Output is correct
32 Correct 20 ms 43380 KB Output is correct
33 Correct 264 ms 48504 KB Output is correct
34 Correct 103 ms 48816 KB Output is correct
35 Correct 237 ms 47344 KB Output is correct
36 Correct 396 ms 52084 KB Output is correct
37 Correct 35 ms 46032 KB Output is correct
38 Correct 434 ms 53036 KB Output is correct
39 Correct 477 ms 53144 KB Output is correct
40 Correct 459 ms 53056 KB Output is correct
41 Correct 460 ms 53044 KB Output is correct
42 Correct 449 ms 53056 KB Output is correct
43 Correct 460 ms 53044 KB Output is correct
44 Correct 439 ms 53072 KB Output is correct
45 Correct 390 ms 53036 KB Output is correct
46 Correct 417 ms 53048 KB Output is correct
47 Correct 417 ms 53044 KB Output is correct
48 Correct 146 ms 50112 KB Output is correct
49 Correct 158 ms 51344 KB Output is correct
50 Correct 65 ms 45320 KB Output is correct
51 Correct 88 ms 46596 KB Output is correct
52 Correct 40 ms 45152 KB Output is correct
53 Correct 201 ms 51924 KB Output is correct
54 Correct 146 ms 47356 KB Output is correct
55 Correct 338 ms 50324 KB Output is correct
56 Correct 234 ms 47960 KB Output is correct
57 Correct 284 ms 51488 KB Output is correct
58 Correct 42 ms 46624 KB Output is correct
59 Correct 70 ms 46368 KB Output is correct
60 Correct 138 ms 50416 KB Output is correct
61 Correct 142 ms 50876 KB Output is correct
62 Correct 94 ms 49128 KB Output is correct
63 Correct 60 ms 49684 KB Output is correct
64 Correct 63 ms 51296 KB Output is correct
65 Correct 81 ms 55620 KB Output is correct
66 Correct 80 ms 46444 KB Output is correct
67 Correct 79 ms 51964 KB Output is correct
68 Correct 139 ms 55536 KB Output is correct
69 Correct 47 ms 44632 KB Output is correct
70 Correct 26 ms 43572 KB Output is correct
71 Correct 69 ms 49308 KB Output is correct
72 Correct 96 ms 54100 KB Output is correct
73 Correct 204 ms 58544 KB Output is correct
74 Correct 228 ms 55088 KB Output is correct
75 Correct 165 ms 58528 KB Output is correct
76 Correct 147 ms 57272 KB Output is correct
77 Correct 241 ms 55348 KB Output is correct