| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1097805 | Neco_arc | Cats or Dogs (JOI18_catdog) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "catdog.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "Cats or Dogs"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7
using namespace std;
const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r)(rng);
}
int n;
int cl[maxn], last[maxn];
int In[maxn], nex[maxn], par[maxn], siz[maxn];
vector<int> edges[maxn];
int dfs_siz(int u) {
siz[u] = 1;
for(int v : edges[u]) {
edges[v].erase(find(all(edges[v]), u));
siz[u] += dfs_siz(v);
if(siz[v] > siz[edges[u][0]]) swap(v, edges[u][0]);
}
return siz[u];
}
void dfs_hld(int u) {
static int Time = 0;
In[u] = ++Time;
for(int v : edges[u]) {
par[v] = u;
nex[v] = v == edges[u][0] ? nex[u] : v;
dfs_hld(v);
}
}
struct IT {
struct Node {
int a[2][2];
Node() { a[0][0] = a[1][1] = 0, a[0][1] = a[1][0] = 1e9; }
} st[4 * maxn];
Node cb(const Node &x, const Node &y) {
Node ans; memset(ans.a, 60, sizeof ans.a);
fi(i, 0, 1) fi(j, 0, 1) fi(u, 0, 1) fi(v, 0, 1) {
ans.a[i][v] = min(ans.a[i][v], x.a[i][j] + y.a[u][v] + (j != u));
}
return ans;
}
void update(int x, int val0, int val1, int id = 1, int l = 1, int r = n) {
if(l > x || r < x) return;
if(l == r) {
st[id].a[0][0] += val0, st[id].a[1][1] += val1;
return;
}
int mid = (l + r) >> 1;
update(x, val0, val1, _left), update(x, val0, val1, _right);
st[id] = cb(st[id * 2], st[id * 2 + 1]);
}
Node get(int u, int v, int id, int l, int r) {
if(l > v || r < u) return Node();
if(u <= l && r <= v) return st[id];
int mid = (l + r) >> 1;
return cb(get(u, v, _left), get(u, v, _right));
}
void get(int u, int v, int &A, int &B) {
Node p = get(u, v, 1, 1, n);
int x0 = min(p.a[0][1], p.a[0][0]);
int x1 = min(p.a[1][0], p.a[1][1]);
A = min(x0, x1 + 1);
B = min(x0 + 1, x1);
}
} St;
void update(int u, int col, int dt0, int dt1) {
cl[u] = col;
while(u) {
int old0, old1, nw0, nw1;
St.get(In[nex[u]], last[nex[u]], old0, old1);
St.update(In[u], dt0, dt1);
St.get(In[nex[u]], last[nex[u]], nw0, nw1);
dt0 = nw0 - old0, dt1 = nw1 - old1;
u = par[nex[u]];
}
}
int get() {
int ans0, ans1; St.get(In[1], last[1], ans0, ans1);
return min(ans0, ans1);
}
int cat(int u) {
update(u, 0, 0, 1e9);
return get();
}
int dog(int u) {
update(u, 1, 1e9, 0);
return get();
}
int neighbor(int u) {
if(cl[u]) update(u, -1, -1e9, 0);
else update(u, -1, 0, -1e9);
return get();
}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
fi(i, 0, n - 2) {
edges[A[i]].push_back(B[i]), edges[B[i]].push_back(A[i]);
}
nex[1] = 1;
dfs_siz(1), dfs_hld(1);
fi(i, 1, n) last[nex[i]] = max(last[nex[i]], In[i]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(Neco".inp", "r")) {
freopen(Neco".inp", "r", stdin);
freopen(Neco".out", "w", stdout);
}
int nTest = 1;
// cin >> nTest;
while(nTest--)
{
solve();
}
return 0;
}