| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 489457 | qwe854896 | Cats or Dogs (JOI18_catdog) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int ll
#define endl '\n'
#define pb emplace_back
#define LC(i) (i << 1)
#define RC(i) ((i << 1) | 1)
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr)
using ll = long long;
using vi = vector <int>;
const ll INF = 1000000007;
const int V = 200005;
/* Helper */
void chmin(int& a, int b) {
if (b < a) a = b;
}
void chmax(int& a, int b) {
if (b > a) a = b;
}
/* Graph */
int n;
vi g[V];
/* Segment Tree */
struct SegTree {
struct Node {
int c[2][2]; // cat/dog cat/dog
Node() {
c[0][0] = c[1][1] = 0;
c[0][1] = c[1][0] = INF;
}
void update(int x, int y) {
c[0][0] += x;
c[1][1] += y;
}
};
int n;
vector <Node> node;
void init(int n) {
this->n = n;
node.resize(n << 3);
}
void pull(int i) {
for (int a = 0; a < 2; ++a)
for (int b = 0; b < 2; ++b)
node[i].c[a][b] = INF;
for (int a = 0; a < 2; ++a)
for (int b = 0; b < 2; ++b)
for (int c = 0; c < 2; ++c)
for (int d = 0; d < 2; ++d)
chmin(node[i].c[a][b], node[LC(i)].c[a][c] + (c ^ d) + node[RC(i)].c[d][b]);
}
int ui, x, y;
void update(int i, int l, int r) {
if (ui < l || r < ui) return;
if (l == r) {
node[i].update(x, y);
return;
}
int m = (l + r) >> 1;
update(LC(i), l, m);
update(RC(i), m + 1, r);
pull(i);
}
void update(int i, int x, int y, int &a, int &b) {
ui = i;
this->x = x;
this->y = y;
update(1, 0, n - 1);
query(a, b);
}
void query(int &x, int &y) {
int c = min(node[1].c[0][0], node[1].c[0][1]);
int d = min(node[1].c[1][0], node[1].c[1][1]);
x = min(c, d + 1);
y = min(c + 1, d);
}
};
vector <SegTree> tree;
/* HLD */
int dep[V], sz[V], hs[V], p[V];
int pdfs(int x, int px) {
sz[x] = 1;
p[x] = px;
int h = 0;
for (int y : g[x])
if (y != px) {
dep[y] = dep[x] + 1;
sz[x] += pdfs(y, x);
if (sz[y] > h)
h = sz[y], hs[x] = y;
}
return sz[x];
}
int g_tp[V], g_sz[V];
int g_cnt, v_num[V];
int pos[V];
void hdfs(int x, int px, int num) {
pos[x] = g_sz[num]++;
v_num[x] = num;
if (hs[x] != -1)
hdfs(hs[x], x, num);
for (int y : g[x])
if (y != px && y != hs[x])
hdfs(y, x, ++g_cnt), g_tp[g_cnt] = y;
}
void initialize(int N, vi A, vi B) {
n = N;
for (int i = n - 2; i >= 0; --i)
g[--A[i]].pb(--B[i]), g[B[i]].pb(A[i]);
for (int i = 0; i < n; ++i)
hs[i] = -1;
pdfs(0, -1);
hdfs(0, 0, 0);
++g_cnt;
tree.resize(g_cnt);
for (int i = 0; i < g_cnt; ++i)
tree[i].init(g_sz[i]);
}
int update(int i, int x, int y) {
while (i != -1) {
int id, old_x, old_y, new_x, new_y;
id = v_num[i];
tree[id].query(old_x, old_y);
tree[id].update(pos[i], x, y, new_x, new_y);
x = new_x - old_x;
y = new_y - old_y;
i = p[g_tp[id]];
}
int a, b;
tree[0].query(a, b);
return min(a, b);
}
int st[V];
int cat(int v) {
--v;
st[v] = 1;
return update(v, 0, INF);
}
int dog(int v) {
--v;
st[v] = 2;
return update(v, INF, 0);
}
int neighbor(int v) {
--v;
int ans;
if (st[v] == 1)
ans = update(v, 0, -INF);
else
ans = update(v, -INF, 0);
st[v] = 0;
return ans;
}