| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 894129 |
2023-12-28T01:40:14 Z |
box |
Cats or Dogs (JOI18_catdog) |
C++17 |
|
2 ms |
7004 KB |
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
const int MAXN = 1e5;
const int INF = 1e6;
int N;
vector<int> adj[MAXN];
bool has[MAXN][2];
int root[MAXN], depth[MAXN], child[MAXN], parent[MAXN], sz[MAXN];
ar<i64, 2> light[MAXN];
using info = ar<ar<int, 2>, 2>;
info operator+(const info one, const info two) {
info me;
for (int x : {0,1}) for (int y : {0,1})
me[x][y] = min(INF,
min(min(one[x][0] + two[0][y], one[x][1] + two[1][y]),
1 + min(one[x][0] + two[1][y], one[x][1] + two[0][y])));
// cout << "ONE " << one[0][0] << ' ' << one[0][1] << ' ' << one[1][0] << ' ' << one[1][1] << endl;
// cout << "TWO " << two[0][0] << ' ' << two[0][1] << ' ' << two[1][0] << ' ' << two[1][1] << endl;
// cout << "ME " << me[0][0] << ' ' << me[0][1] << ' ' << me[1][0] << ' ' << me[1][1] << endl;
return me;
}
struct segt {
int l, r;
segt *lc, *rc;
info x;
segt(int l, int r) : l(l), r(r) {
x = {};
if (l < r) {
int m = (l + r) / 2;
lc = new segt(l, m);
rc = new segt(m + 1, r);
} else x[1][0] = x[0][1] = INF;
}
void upd(int i, const ar<int, 2> &v) {
if (l == r) x = {ar<int, 2>{v[0], INF}, ar<int, 2>{INF, v[1]}};
else {
i <= lc->r ? lc->upd(i, v) : rc->upd(i, v);
x = lc->x + rc->x;
}
// cout << l << " " << r << endl;
// cout << "GOT " << x[0][0] << ' ' << x[0][1] << ' ' << x[1][0] << ' ' << x[1][1] << endl;
}
ar<int, 2> pack() {
return {min(x[0][0], x[0][1]), min(x[1][0], x[1][1])};
}
} *tree[MAXN];
int dfs_sz(int i) {
int s = 1, x = 0;
child[i] = -1;
for (int j : adj[i]) if (parent[i] != j) {
depth[j] = depth[i] + 1;
parent[j] = i;
int y = dfs_sz(j);
if (y > x) {
x = y;
child[i] = j;
}
s += y;
}
return s;
}
void dfs_hvy(int r, int i) {
cout << "GOT " << i+1 << " => " << r+1 << endl;
++sz[root[i] = r];
if (~child[i]) dfs_hvy(r, child[i]);
for (int j : adj[i]) if (parent[i] != j && child[i] != j) dfs_hvy(j, j);
}
void initialize(int N, vector<int> A, vector<int> B) {
for (int h = 0; h < N - 1; h++) {
auto [i, j] = make_pair(A[h], B[h]);
i--, j--;
adj[i].push_back(j);
adj[j].push_back(i);
}
parent[0] = -1;
dfs_sz(0);
dfs_hvy(0, 0);
for (int i = 0; i < N; i++) if (sz[i]) {
tree[i] = new segt(0, sz[i] - 1);
cout << "at root " << i+1 << ", got size " << sz[i] << endl;
}
}
int pul(int i) {
while (~i) {
int r = root[i];
int p = parent[r];
if (~p) {
auto v = tree[r]->pack();
light[p][0] -= min(v[0], v[1] + 1), light[p][1] -= min(v[0] + 1, v[1]);
}
tree[r]->upd(depth[i] - depth[r], {int(min(light[i][0], i64(INF))), int(min(light[i][1], i64(INF)))});
if (~p) {
auto v = tree[r]->pack();
light[p][0] += min(v[0], v[1] + 1), light[p][1] += min(v[0] + 1, v[1]);
}
i = p;
}
auto v = tree[0]->pack();
return min(v[0], v[1]);
}
int cat(int i) {
i--;
has[i][0] = 1;
light[i][0] += INF;
return pul(i);
}
int dog(int i) {
i--;
has[i][1] = 1;
light[i][1] += INF;
return pul(i);
}
int neighbor(int i) {
i--;
if (has[i][0]) light[i][0] -= INF, has[i][0] = 0;
if (has[i][1]) light[i][1] -= INF, has[i][1] = 0;
return pul(i);
}
#ifdef LOCAL
int main() {
int N;
cin >> N;
vector<int> A(N-1, 0), B(N-1, 0);
for (int i = 0; i < N-1; i++) cin >> A[i] >> B[i];
initialize(N, A, B);
int Q;
cin >> Q;
while (Q--) {
int t, i;
cin >> t >> i;
cout << (t == 1 ? cat : t == 2 ? dog : neighbor)(i) << '\n';
for (int i = 0; i < N; i++) cout << light[i][0] << ' ' << light[i][1] << '\n';
cout << endl;
}
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
7004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
