oj.uz

Submission #492980

# Submission time Handle Problem Language Result Execution time Memory
492980 2021-12-09T21:37:54 Z ivan_tudor Cats or Dogs (JOI18_catdog) C++14
38 / 100
 259 ms 46132 KB 
#include "catdog.h"
#include<assert.h>
using namespace std;
const int N = 200005;
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 9 ms 17544 KB Output is correct
2 Correct 8 ms 17484 KB Output is correct
3 Correct 8 ms 17484 KB Output is correct
4 Correct 8 ms 17484 KB Output is correct
5 Correct 9 ms 17484 KB Output is correct
6 Correct 11 ms 17484 KB Output is correct
7 Correct 8 ms 17484 KB Output is correct
8 Correct 9 ms 17484 KB Output is correct
9 Correct 9 ms 17440 KB Output is correct
10 Correct 9 ms 17452 KB Output is correct
11 Correct 9 ms 17484 KB Output is correct
12 Correct 9 ms 17484 KB Output is correct
13 Correct 8 ms 17484 KB Output is correct
14 Correct 8 ms 17444 KB Output is correct
15 Correct 8 ms 17552 KB Output is correct
16 Correct 9 ms 17484 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17544 KB Output is correct
2 Correct 8 ms 17484 KB Output is correct
3 Correct 8 ms 17484 KB Output is correct
4 Correct 8 ms 17484 KB Output is correct
5 Correct 9 ms 17484 KB Output is correct
6 Correct 11 ms 17484 KB Output is correct
7 Correct 8 ms 17484 KB Output is correct
8 Correct 9 ms 17484 KB Output is correct
9 Correct 9 ms 17440 KB Output is correct
10 Correct 9 ms 17452 KB Output is correct
11 Correct 9 ms 17484 KB Output is correct
12 Correct 9 ms 17484 KB Output is correct
13 Correct 8 ms 17484 KB Output is correct
14 Correct 8 ms 17444 KB Output is correct
15 Correct 8 ms 17552 KB Output is correct
16 Correct 9 ms 17484 KB Output is correct
17 Correct 9 ms 17612 KB Output is correct
18 Correct 10 ms 17612 KB Output is correct
19 Correct 10 ms 17612 KB Output is correct
20 Correct 12 ms 17572 KB Output is correct
21 Correct 10 ms 17512 KB Output is correct
22 Correct 9 ms 17588 KB Output is correct
23 Correct 11 ms 17576 KB Output is correct
24 Correct 11 ms 17612 KB Output is correct
25 Correct 13 ms 17484 KB Output is correct
26 Correct 9 ms 17484 KB Output is correct
27 Correct 8 ms 17484 KB Output is correct
28 Correct 9 ms 17612 KB Output is correct
29 Correct 10 ms 17612 KB Output is correct
30 Correct 9 ms 17484 KB Output is correct
31 Correct 8 ms 17612 KB Output is correct
32 Correct 9 ms 17484 KB Output is correct

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17544 KB Output is correct
2 Correct 8 ms 17484 KB Output is correct
3 Correct 8 ms 17484 KB Output is correct
4 Correct 8 ms 17484 KB Output is correct
5 Correct 9 ms 17484 KB Output is correct
6 Correct 11 ms 17484 KB Output is correct
7 Correct 8 ms 17484 KB Output is correct
8 Correct 9 ms 17484 KB Output is correct
9 Correct 9 ms 17440 KB Output is correct
10 Correct 9 ms 17452 KB Output is correct
11 Correct 9 ms 17484 KB Output is correct
12 Correct 9 ms 17484 KB Output is correct
13 Correct 8 ms 17484 KB Output is correct
14 Correct 8 ms 17444 KB Output is correct
15 Correct 8 ms 17552 KB Output is correct
16 Correct 9 ms 17484 KB Output is correct
17 Correct 9 ms 17612 KB Output is correct
18 Correct 10 ms 17612 KB Output is correct
19 Correct 10 ms 17612 KB Output is correct
20 Correct 12 ms 17572 KB Output is correct
21 Correct 10 ms 17512 KB Output is correct
22 Correct 9 ms 17588 KB Output is correct
23 Correct 11 ms 17576 KB Output is correct
24 Correct 11 ms 17612 KB Output is correct
25 Correct 13 ms 17484 KB Output is correct
26 Correct 9 ms 17484 KB Output is correct
27 Correct 8 ms 17484 KB Output is correct
28 Correct 9 ms 17612 KB Output is correct
29 Correct 10 ms 17612 KB Output is correct
30 Correct 9 ms 17484 KB Output is correct
31 Correct 8 ms 17612 KB Output is correct
32 Correct 9 ms 17484 KB Output is correct
33 Correct 259 ms 22636 KB Output is correct
34 Correct 103 ms 22980 KB Output is correct
35 Correct 228 ms 21588 KB Output is correct
36 Runtime error 97 ms 46132 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -