oj.uz

Submission #920984

# Submission time Handle Problem Language Result Execution time Memory
920984 2024-02-03T08:40:13 Z KiaRez Cats or Dogs (JOI18_catdog) C++17
8 / 100
 10 ms 24668 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 17;
ll Mod = 998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

struct node {
	int dp[2][2];
	node() {dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=0; dp[0][1]=dp[1][0]=N;}
} seg[N];

node merge(node x, node y) {
	node z;
	for(int i=0; i<2; i++) {
	for(int j=0; j<2; j++) { 
z.dp[i][j] = min({x.dp[i][1]+y.dp[1][j], x.dp[i][0]+y.dp[0][j], x.dp[i][0]+y.dp[1][j]+1, 1+x.dp[i][1]+y.dp[0][j]});
	}
	}
	return z;
}

int n, tim, dwn[N], tin[N], tout[N], par[N], head[N], h[N], subt[N], typ[N];
int ttmp[2][2][N];
vector<int> adj[N];

void init(int v, int p=0) {
	par[v]=p, h[v]=h[p]+1, subt[v]=1;
	for(int u : adj[v]) {
		if(u == p) continue;
		init(u, v); subt[v] += subt[u];
	}
}

void dfs(int v, int p) {
	int mx = 0;
	tin[v] = ++tim, head[v] = p, dwn[p] = v;
	for(int u : adj[v]) if(u!=par[v]) mx = (subt[mx] > subt[u] ? mx : u);
	if(mx > 0) dfs(mx, p);
	for(int u : adj[v]) if(u!=par[v] && u!=mx) dfs(u, u);
	tout[v] = tim+1;
}

void update(int ind, node val) {
	if(ind == 0) return;
	if(ind >= (1<<lg)) {
		seg[ind] = val;
	} else {
		seg[ind] = merge(seg[2*ind], seg[2*ind+1]);
	}
	update(ind/2, val);
}

node query(int l, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) {
	if(lc>=l && rc<=r) return seg[ind];
	int mid = (lc+rc)/2;
	if(r<=mid) return query(l, r, 2*ind, lc, mid);
	if(l>=mid) return query(l, r, 2*ind+1, mid, rc);
	return merge(query(l, r, 2*ind, lc, mid), query(l, r, 2*ind+1, mid, rc));
}

void initialize(int _n, vector<int> A, vector<int> B) {
	n=_n;
	for(int i=0; i<n-1; i++) adj[A[i]].pb(B[i]), adj[B[i]].pb(A[i]);
	init(1);
	dfs(1, 1);
}

int ftmp[N][2][2];
void reinit(int v) {
	int u = v;
	node ct;
	while(head[v] != 1) {
		ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
		node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
		v=par[head[v]];
		ftmp[0][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ftmp[1][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ftmp[0][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		ftmp[1][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		update(tin[v]+(1<<lg)-1, tmp);
	}

	v = u;
	while(head[v] != 1) {
		ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
		node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
		v=par[head[v]];
		tmp.dp[0][0] -= ftmp[0][0][tin[v]];
		tmp.dp[1][0] -= ftmp[1][0][tin[v]];
		tmp.dp[0][1] -= ftmp[0][1][tin[v]];
		tmp.dp[1][1] -= ftmp[1][1][tin[v]];
		ttmp[0][0][tin[v]] -= ftmp[0][0][tin[v]];
		ttmp[1][0][tin[v]] -= ftmp[1][0][tin[v]];
		ttmp[0][1][tin[v]] -= ftmp[0][1][tin[v]];
		ttmp[1][1][tin[v]] -= ftmp[1][1][tin[v]];
		update(tin[v]+(1<<lg)-1, tmp);
		for(int i=0; i<2; i++) for(int j=0; j<2; j++) ftmp[i][j][tin[v]] = 0;
	}
}

int cat(int v) {
	reinit(v);
	typ[v] = 1;
	
	node ct;
	ct.dp[1][0]=ct.dp[1][1]=ct.dp[0][1]=n;
	if(v==head[v]) ct.dp[1][0] = 1;
	if(v==dwn[head[v]]) ct.dp[0][1] = 1;
	for(int i=0; i<2; i++) for(int j=0; j<2; j++) ct.dp[i][j] += ttmp[i][j][tin[v]];
	update(tin[v]+(1<<lg)-1, ct);
	while(head[v] != 1) {
		ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
		node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
		tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		v=par[head[v]];
		ttmp[0][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[1][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[0][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		ttmp[1][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		update(tin[v]+(1<<lg)-1, tmp);
	}

	ct = query(tin[1], tin[dwn[1]]+1);
	return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]});
}

int dog(int v) {
	reinit(v);
	typ[v] = 2;

	node ct;
	ct.dp[1][0]=ct.dp[0][0]=ct.dp[0][1]=n;
	if(v==head[v]) ct.dp[0][1] = 1;
	if(v==dwn[head[v]]) ct.dp[1][0] = 1;
	for(int i=0; i<2; i++) for(int j=0; j<2; j++) ct.dp[i][j] += ttmp[i][j][tin[v]];
	update(tin[v]+(1<<lg)-1, ct);
	while(head[v] != 1) {
		ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
		node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
		tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		v=par[head[v]];
		ttmp[0][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[1][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[0][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		ttmp[1][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		update(tin[v]+(1<<lg)-1, tmp);
	}

	ct = query(tin[1], tin[dwn[1]]+1);
	return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]});
}

int neighbor(int v) {
	reinit(v);
	typ[v] = 0;

	node ct;
	if(v==head[v] || v==dwn[head[v]]) ct.dp[0][1] = 1, ct.dp[1][0] = 1;
	for(int i=0; i<2; i++) for(int j=0; j<2; j++) ct.dp[i][j] += ttmp[i][j][tin[v]];
	update(tin[v]+(1<<lg)-1, ct);
	while(head[v] != 1) {
		ct = query(tin[head[v]], tin[dwn[head[v]]]+1);
		node tmp = query(tin[par[head[v]]], tin[par[head[v]]]+1);
		tmp.dp[0][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[1][0] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		tmp.dp[0][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		tmp.dp[1][1] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		v=par[head[v]];
		ttmp[0][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[1][0][tin[v]] += min({ct.dp[1][0]+1, ct.dp[1][1]+1, ct.dp[0][1], ct.dp[0][0]});
		ttmp[0][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		ttmp[1][1][tin[v]] += min({ct.dp[0][1]+1, ct.dp[0][0]+1, ct.dp[1][0], ct.dp[1][1]});
		update(tin[v]+(1<<lg)-1, tmp);
	}

	ct = query(tin[1], tin[dwn[1]]+1);
	return min({ct.dp[0][0], ct.dp[0][1], ct.dp[1][1], ct.dp[1][0]});
}

/*
int main () {

	initialize(7, {1, 2, 3, 1, 5, 1}, {2, 3, 4, 5, 6, 7});
	
	cout<< cat(1)<<endl;
	cout<< dog(5)<<endl;
	cout<< dog(4)<<endl;
	cout<< dog(2)<<endl;
	cout<< dog(7)<<endl;
	cout<< dog(3)<<endl;
	cout<< dog(6)<<endl;
	cout<< neighbor(1)<<endl;
	
	// tmp2 = merge(tmp2, tmp1);
	// fuck(tmp2.dp[0][0]);
	// fuck(tmp2.dp[1][0]);
	// fuck(tmp2.dp[0][1]);
	// fuck(tmp2.dp[1][1]);

	return 0;
}
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22364 KB Output is correct
2 Correct 5 ms 24408 KB Output is correct
3 Correct 6 ms 24408 KB Output is correct
4 Correct 6 ms 22540 KB Output is correct
5 Correct 6 ms 24412 KB Output is correct
6 Correct 5 ms 22364 KB Output is correct
7 Correct 5 ms 24412 KB Output is correct
8 Correct 5 ms 24412 KB Output is correct
9 Correct 5 ms 22364 KB Output is correct
10 Correct 9 ms 24532 KB Output is correct
11 Correct 5 ms 22364 KB Output is correct
12 Correct 4 ms 22360 KB Output is correct
13 Correct 6 ms 22364 KB Output is correct
14 Correct 5 ms 22364 KB Output is correct
15 Correct 7 ms 24412 KB Output is correct
16 Correct 5 ms 24412 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22364 KB Output is correct
2 Correct 5 ms 24408 KB Output is correct
3 Correct 6 ms 24408 KB Output is correct
4 Correct 6 ms 22540 KB Output is correct
5 Correct 6 ms 24412 KB Output is correct
6 Correct 5 ms 22364 KB Output is correct
7 Correct 5 ms 24412 KB Output is correct
8 Correct 5 ms 24412 KB Output is correct
9 Correct 5 ms 22364 KB Output is correct
10 Correct 9 ms 24532 KB Output is correct
11 Correct 5 ms 22364 KB Output is correct
12 Correct 4 ms 22360 KB Output is correct
13 Correct 6 ms 22364 KB Output is correct
14 Correct 5 ms 22364 KB Output is correct
15 Correct 7 ms 24412 KB Output is correct
16 Correct 5 ms 24412 KB Output is correct
17 Correct 7 ms 22620 KB Output is correct
18 Correct 10 ms 24668 KB Output is correct
19 Correct 8 ms 24668 KB Output is correct
20 Correct 5 ms 22620 KB Output is correct
21 Correct 7 ms 24668 KB Output is correct
22 Correct 7 ms 24668 KB Output is correct
23 Incorrect 8 ms 22632 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22364 KB Output is correct
2 Correct 5 ms 24408 KB Output is correct
3 Correct 6 ms 24408 KB Output is correct
4 Correct 6 ms 22540 KB Output is correct
5 Correct 6 ms 24412 KB Output is correct
6 Correct 5 ms 22364 KB Output is correct
7 Correct 5 ms 24412 KB Output is correct
8 Correct 5 ms 24412 KB Output is correct
9 Correct 5 ms 22364 KB Output is correct
10 Correct 9 ms 24532 KB Output is correct
11 Correct 5 ms 22364 KB Output is correct
12 Correct 4 ms 22360 KB Output is correct
13 Correct 6 ms 22364 KB Output is correct
14 Correct 5 ms 22364 KB Output is correct
15 Correct 7 ms 24412 KB Output is correct
16 Correct 5 ms 24412 KB Output is correct
17 Correct 7 ms 22620 KB Output is correct
18 Correct 10 ms 24668 KB Output is correct
19 Correct 8 ms 24668 KB Output is correct
20 Correct 5 ms 22620 KB Output is correct
21 Correct 7 ms 24668 KB Output is correct
22 Correct 7 ms 24668 KB Output is correct
23 Incorrect 8 ms 22632 KB Output isn't correct
24 Halted 0 ms 0 KB -