oj.uz

Submission #415773

# Submission time Handle Problem Language Result Execution time Memory
415773 2021-06-01T13:38:58 Z MarcoMeijer Cats or Dogs (JOI18_catdog) C++14
8 / 100
 72 ms 66932 KB 
#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second

const int INF	= 1e6;
const int MX	= 200;
const int N	  = 1<<20;
const int MOD	= 1e9+7;

int n;
int a[MX];

// tree stuff
vi adj[MX], chl[MX];
int sz[MX], par[MX], dep[MX];
void dfs(int u, int p) {
  sz[u] = 1;
  par[u] = p;
  dep[u] = dep[p]+1;
  FOR(v,adj[u]) {
    if(v == p) continue;
    dfs(v,u);
    sz[u] += sz[v];
    chl[u].pb(v);
  }
}

// hld
int hd[MX], tl[MX], segi[MX], curseg=0;
void HLD(int u, int head) {
  hd[u] = head;
  segi[u] = curseg++;
  tl[head] = u;
  tl[u] = u;
  if(chl[u].empty()) return;
  int bst = chl[u][0];
  FOR(v,chl[u]) if(sz[v]>sz[bst]) bst = v;
  HLD(bst,head);
  FOR(v,chl[u]) if(v != bst) HLD(v,v);
  tl[u] = tl[head];
}

// seg
struct T {
  T() {
    RE(j,2) a[j][ j] = 0;
    RE(j,2) a[j][!j] = INF;
  }
  int a[2][2];
};
T seg[N*2];
T combine(T a, T b) {
  T res;
  RE(i,2) RE(j,2) res.a[i][j] = INF;
  RE(i,2) RE(j,2) RE(k,2) RE(l,2)
    res.a[i][l] = min(res.a[i][l], a.a[i][j] + b.a[k][l] + (j==k?0:1));
  return res;
}
void combine(int p) {
  seg[p] = combine(seg[p*2], seg[p*2+1]);
}
void buildSeg(int p=1, int l=0, int r=N-1) {
  if(l == r) {
    RE(j,2) seg[p].a[j][ j] = 0;
    RE(j,2) seg[p].a[j][!j] = INF;
    return;
  }
  int m=(l+r)/2;
  buildSeg(p*2,l,m);
  buildSeg(p*2+1,m+1,r);
  combine(p);
}
void addSeg(int i, int x, int v, int p=1, int l=0, int r=N-1) {
  if(i < l || i > r) return;
  if(l == r) {
    seg[p].a[x][x] += v;
    return;
  }
  int m=(l+r)/2;
  addSeg(i,x,v,p*2,l,m);
  addSeg(i,x,v,p*2+1,m+1,r);
  combine(p);
}
T getSeg(int i, int j, int p=1, int l=0, int r=N-1) {
  if(j < l || i > r) return {};
  if(i <= l && j >= r) return seg[p];
  int m=(l+r)/2;
  T a=getSeg(i,j,p*2,l,m);
  T b=getSeg(i,j,p*2+1,m+1,r);
  return combine(a,b);
}

// updates
int ans=0;
int getRes(T a, int x) {
  return min(a.a[x][0], a.a[x][1]);
}
void update(int u, int v1, int v2) {
  while(true) {
    T oldValue = getSeg(segi[hd[u]], segi[tl[u]]);
    addSeg(segi[u], 0, v1);
    addSeg(segi[u], 1, v2);
    T newValue = getSeg(segi[hd[u]], segi[tl[u]]);
    if(hd[u] == 1) {
      ans = INF;
      RE(i,2) RE(j,2) ans = min(ans, newValue.a[i][j]);
      break;
    } else {
      v1 = getRes(newValue,0) - getRes(oldValue,0);
      v2 = getRes(newValue,1) - getRes(oldValue,1);
      u = par[hd[u]];
    }
  }
}

// init
void initialize(int N, std::vector<int> A, std::vector<int> B) {
  n = N;
  RE(i,n-1) {
    adj[A[i]].pb(B[i]);
    adj[B[i]].pb(A[i]);
  }
  dfs(1,1);
  HLD(1,1);
  buildSeg();
}

// interaction
int cat(int v) {
  a[v] = 1;
  update(v,INF,0);
  return ans;
}
int dog(int v) {
  a[v] = 2;
  update(v,0,INF);
  return ans;
}
int neighbor(int v) {
  if(a[v] == 1) update(v,-INF,0);
  if(a[v] == 2) update(v,0,-INF);
  a[v] = 0;
  return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 33100 KB Output is correct
2 Correct 67 ms 33124 KB Output is correct
3 Correct 59 ms 33016 KB Output is correct
4 Correct 69 ms 33120 KB Output is correct
5 Correct 60 ms 33116 KB Output is correct
6 Correct 70 ms 33120 KB Output is correct
7 Correct 67 ms 33056 KB Output is correct
8 Correct 61 ms 33040 KB Output is correct
9 Correct 57 ms 33136 KB Output is correct
10 Correct 61 ms 33128 KB Output is correct
11 Correct 61 ms 33020 KB Output is correct
12 Correct 58 ms 33124 KB Output is correct
13 Correct 62 ms 33100 KB Output is correct
14 Correct 62 ms 33116 KB Output is correct
15 Correct 59 ms 33040 KB Output is correct
16 Correct 72 ms 33128 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 33100 KB Output is correct
2 Correct 67 ms 33124 KB Output is correct
3 Correct 59 ms 33016 KB Output is correct
4 Correct 69 ms 33120 KB Output is correct
5 Correct 60 ms 33116 KB Output is correct
6 Correct 70 ms 33120 KB Output is correct
7 Correct 67 ms 33056 KB Output is correct
8 Correct 61 ms 33040 KB Output is correct
9 Correct 57 ms 33136 KB Output is correct
10 Correct 61 ms 33128 KB Output is correct
11 Correct 61 ms 33020 KB Output is correct
12 Correct 58 ms 33124 KB Output is correct
13 Correct 62 ms 33100 KB Output is correct
14 Correct 62 ms 33116 KB Output is correct
15 Correct 59 ms 33040 KB Output is correct
16 Correct 72 ms 33128 KB Output is correct
17 Runtime error 68 ms 66932 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 33100 KB Output is correct
2 Correct 67 ms 33124 KB Output is correct
3 Correct 59 ms 33016 KB Output is correct
4 Correct 69 ms 33120 KB Output is correct
5 Correct 60 ms 33116 KB Output is correct
6 Correct 70 ms 33120 KB Output is correct
7 Correct 67 ms 33056 KB Output is correct
8 Correct 61 ms 33040 KB Output is correct
9 Correct 57 ms 33136 KB Output is correct
10 Correct 61 ms 33128 KB Output is correct
11 Correct 61 ms 33020 KB Output is correct
12 Correct 58 ms 33124 KB Output is correct
13 Correct 62 ms 33100 KB Output is correct
14 Correct 62 ms 33116 KB Output is correct
15 Correct 59 ms 33040 KB Output is correct
16 Correct 72 ms 33128 KB Output is correct
17 Runtime error 68 ms 66932 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -