oj.uz

Submission #125082

# Submission time Handle Problem Language Result Execution time Memory
125082 2019-07-04T14:49:07 Z WhipppedCream Cats or Dogs (JOI18_catdog) C++17
38 / 100
 3000 ms 36840 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;

int n;

struct fenwick
{
	ll ft[maxn];
	ll sum(int x)
	{
		ll res = 0;
		for(; x; x -= x&(-x)) res += ft[x];
		return res;
	}
	void change(int x, int dx)
	{
		for(; x<= n; x += x&(-x)) ft[x] += dx;
	}
	ll ask(int x)
	{
		return sum(x);
	}
	void update(int a, int b, int dx)
	{
		change(a, dx);
		change(b+1, -dx);
	}
};

struct segtree
{
	struct node
	{
		vector<int> vec = vector<int>(3, 0);
		int lz = 0;
		node(){}
		node(vector<int> vec) : vec(vec) {}
	};
	node st[4*maxn];
	void push(int p, int L, int R)
	{
		int &lz = st[p].lz;
		if(!lz) return;
		vector<int> &vec = st[p].vec;
		vector<int> nou(3);
		for(int i = 0; i< 3; i++)
		{
			nou[i] = (0<= i-lz && i-lz< 3)?vec[i-lz]:0;
		}
		vec = nou;
		if(L != R)
		{
			st[2*p].lz += lz;
			st[2*p+1].lz += lz;
		}
		lz = 0;
	}
	node pull(node &x, node &y)
	{
		node res;
		for(int i = 0; i< 3; i++) res.vec[i] = x.vec[i]+y.vec[i];
		return res;
	}
	void build(int p = 1, int L = 1, int R = n)
	{
		if(L == R)
		{
			st[p].vec = {0, 1, 0};
			return;
		}
		int M = (L+R)/2;
		build(2*p, L, M);
		build(2*p+1, M+1, R);
		st[p] = pull(st[2*p], st[2*p+1]);
	}
	node ask(int i, int j, int p = 1, int L = 1, int R = n)
	{
		if(i> R || j< L) return node();
		push(p, L, R);
		if(i<= L && R<= j) return st[p];
		int M = (L+R)/2;
		node x = ask(i, j, 2*p, L, M);
		node y = ask(i, j, 2*p+1, M+1, R);
		node res = pull(x, y);
		return res;
	}
	void update(int i, int j, int dx, int p = 1, int L = 1, int R = n)
	{
		push(p, L, R);
		if(i> R || j< L) return;
		if(i<= L && R<= j)
		{
			st[p].lz += dx;
			push(p, L, R);
			return;
		}
		int M = (L+R)/2;
		update(i, j, dx, 2*p, L, M);
		update(i, j, dx, 2*p+1, M+1, R);
		st[p] = pull(st[2*p], st[2*p+1]);
	}
	void point(int x, int dx, int p = 1, int L = 1, int R = n)
	{
		push(p, L, R);
		if(x> R || x< L) return;
		if(x<= L && R<= x)
		{
			st[p].vec = {0, 0, 0};
			if(0<= dx+1 && dx+1< 3) st[p].vec[dx+1] = 1;
			return;
		}
		int M = (L+R)/2;
		point(x, dx, 2*p, L, M);
		point(x, dx, 2*p+1, M+1, R);
		st[p] = pull(st[2*p], st[2*p+1]);
	}
};

vector<int> adj[maxn];
int par[22][maxn];
int pos[maxn];
int head[maxn];
int prf[maxn];
int cnt[maxn];
int dep[maxn];

void dfs(int u = 1, int p = 0)
{
	dep[u] = dep[p]+1;
	par[0][u] = p;
	for(int i = 1; i<= 20; i++) par[i][u] = par[i-1][par[i-1][u]];
	cnt[u] = 1;
	ii best = {0, -1};
	for(int v : adj[u])
	{
		if(v == p) continue;
		dfs(v, u);
		best = max(best, {cnt[v], v});
		cnt[u] += cnt[v];
	}
	prf[u] = best.Y;
}

void hld()
{
	int tim = 1;
	for(int i = 1; i<= n; i++)
	{
		if(prf[par[0][i]] == i) continue;
		for(int j = i; j != -1; j = prf[j])
		{
			head[j] = i;
			pos[j] = tim++;
		}
	}
}

fenwick Cat, Dog;

ll gimme(fenwick &ft, int x)
{
	return ft.ask(pos[x]);
}

void rangeplus(fenwick &ft, int u, int v, int dx)
{
	if(v == 0) v = 1;
	if(u == 0) return;
	while(head[u] != head[v])
	{
		ft.update(pos[head[u]], pos[u], dx);
		u = par[0][head[u]];
	}
	ft.update(pos[v], pos[u], dx);
}

segtree foo;

vector<int> gim3(int u, int v)
{
	if(u == 0) return {0, 0, 0};
	if(v == 0) v = 1;
	vector<int> res(3, 0);
	while(head[u] != head[v])
	{
		auto tmp = foo.ask(pos[head[u]], pos[u]);
		for(int i = 0; i< 3; i++) res[i] += tmp.vec[i];
		u = par[0][head[u]];
	}
	auto tmp = foo.ask(pos[v], pos[u]);
	for(int i = 0; i< 3; i++) res[i] += tmp.vec[i];
	return res;
}

void shift(int u, int v, int dx)
{
	if(v == 0) v = 1;
	while(head[u] != head[v])
	{
		foo.update(pos[head[u]], pos[u], dx);
		u = par[0][head[u]];
	}
	foo.update(pos[v], pos[u], dx);
}

void spec(int u, int dx)
{
	foo.point(pos[u], dx);
}

int stat[maxn];

void diffcat(int u, int dc, int dd)
{
	if(u == 0) return;
	if(u == 1)
	{
		rangeplus(Cat, u, u, dc);
		rangeplus(Dog, u, u, dd);
		spec(u, stat[u]?1e9:gimme(Cat, u)-gimme(Dog, u));
		return;
	}
	if(dd-dc == 2)
	{
		// printf("KUY\n");
		int cur = u;
		for(int i = 20; i>= 0; i--)
		{
			if(gim3(u, par[i][cur])[2] == dep[u]-dep[par[i][cur]]+1)
			{
				cur = par[i][cur];
			}
		}
		int bad = par[0][cur];
		if(gim3(u, cur)[2] != dep[u]-dep[cur]+1) bad = cur;
		shift(u, bad, dc-dd);
		if(bad)
		{
			ll c = gimme(Cat, bad), d = gimme(Dog, bad);
			if(stat[bad] == 1) d = 1e9;
			if(stat[bad] == 2) c = 1e9;
			// printf("diff = %d\n", (int) (c-d));
			if(c-d> 2) diffcat(par[0][bad], dd, dd);
			else if(c-d == 2) diffcat(par[0][bad], dc+1, dd);
			else if(c-d == 0) diffcat(par[0][bad], dc, dc+1);
			else diffcat(par[0][bad], dc, dc);
			spec(bad, stat[bad]?1e9:gimme(Cat, bad)-gimme(Dog, bad));
		}
		rangeplus(Cat, u, bad, dc);
		rangeplus(Dog, u, bad, dd);
		spec(bad, stat[bad]?1e9:gimme(Cat, bad)-gimme(Dog, bad));
		spec(u, stat[u]?1e9:gimme(Cat, u)-gimme(Dog, u));
		return;
	}
	if(dd-dc == 1)
	{
		int cur = u;
		for(int i = 20; i>= 0; i--)
		{
			auto tmp = gim3(u, par[i][cur]);
			if(tmp[1]+tmp[2] == dep[u]-dep[par[i][cur]]+1)
			{
				cur = par[i][cur];
			}
		}
		int bad = par[0][cur];
		auto ff = gim3(bad, bad);
		// printf("bad1 = %d\n", bad);
		// printf("%d %d %d\n", ff[0], ff[1], ff[2]);
		auto tmp = gim3(u, cur);
		if(tmp[1]+tmp[2] != dep[u]-dep[cur]+1) bad = cur;
		// printf("bad2 = %d\n", bad);
		shift(u, bad, dc-dd);
		if(bad)
		{
			ll c = gimme(Cat, bad), d = gimme(Dog, bad);
			if(stat[bad] == 1) d = 1e9;
			if(stat[bad] == 2) c = 1e9;
			// printf("%lld %lld\n", c, d);
			// printf("d %d %d\n", dc, dd);
			if(c-d> 1)
			{
				diffcat(par[0][bad], dd, dd);
				// printf("KUY\n");
			}
			if(c-d< 0) diffcat(par[0][bad], dc, dc);
		}
		rangeplus(Cat, u, bad, dc);
		rangeplus(Dog, u, bad, dd);
		spec(bad, stat[bad]?1e9:gimme(Cat, bad)-gimme(Dog, bad));
		spec(u, stat[u]?1e9:gimme(Cat, u)-gimme(Dog, u));
		return;
	}
	if(dd-dc == 0)
	{
		rangeplus(Cat, u, 1, dc);
		rangeplus(Dog, u, 1, dd);
		return;
	}
	if(dd-dc == -1)
	{
		int cur = u;
		for(int i = 20; i>= 0; i--)
		{
			auto tmp = gim3(u, par[i][cur]);
			if(tmp[0]+tmp[1] == dep[u]-dep[par[i][cur]]+1)
			{
				cur = par[i][cur];
			}
		}
		int bad = par[0][cur];
		auto tmp = gim3(u, cur);
		if(tmp[0]+tmp[1] != dep[u]-dep[cur]+1) bad = cur;
		shift(u, bad, dc-dd);
		if(bad)
		{
			ll c = gimme(Cat, bad), d = gimme(Dog, bad);
			if(stat[bad] == 1) d = 1e9;
			if(stat[bad] == 2) c = 1e9;
			if(c-d< -1) diffcat(par[0][bad], dc, dc);
			if(c-d> 0) diffcat(par[0][bad], dd, dd);
		}
		rangeplus(Cat, u, bad, dc);
		rangeplus(Dog, u, bad, dd);
		spec(bad, stat[bad]?1e9:gimme(Cat, bad)-gimme(Dog, bad));
		spec(u, stat[u]?1e9:gimme(Cat, u)-gimme(Dog, u));
		return;
	}
	if(dd-dc == -2)
	{
		int cur = u;
		for(int i = 20; i>= 0; i--)
		{
			if(gim3(u, par[i][cur])[0] == dep[u]-dep[par[i][cur]]+1)
			{
				cur = par[i][cur];
			}
		}
		int bad = par[0][cur];
		if(gim3(u, cur)[0] != dep[u]-dep[cur]+1) bad = cur;
		shift(u, bad, dc-dd);
		if(bad)
		{
			ll c = gimme(Cat, bad), d = gimme(Dog, bad);
			if(stat[bad] == 1) d = 1e9;
			if(stat[bad] == 2) c = 1e9;
			if(c-d< -2) diffcat(par[0][bad], dc, dc);
			else if(c-d == -2) diffcat(par[0][bad], dc, dd+1);
			else if(c-d == 0) diffcat(par[0][bad], dd+1, dd);
			else diffcat(par[0][bad], dd, dd);
		}
		rangeplus(Cat, u, bad, dc);
		rangeplus(Dog, u, bad, dd);
		spec(bad, stat[bad]?1e9:gimme(Cat, bad)-gimme(Dog, bad));
		spec(u, stat[u]?1e9:gimme(Cat, u)-gimme(Dog, u));
		return;
	}
}

ll getanswer()
{
	ll c = gimme(Cat, 1);
	ll d = gimme(Dog, 1);
	if(stat[1] == 1) return c;
	if(stat[1] == 2) return d;
	return min(c, d);
}

int cat(int u)
{
	// printf("cat(%d)\n", u);
	stat[u] = 1;
	ll c = gimme(Cat, u), d = gimme(Dog, u);
	if(c == d) diffcat(par[0][u], 0, 1);
	if(c> d) diffcat(par[0][u], c-d-1, c-d-1+2);
	spec(u, 1e9);
	return (int) getanswer();
}

int dog(int u)
{
	// printf("dog(%d)\n", u);
	stat[u] = 2;
	ll c = gimme(Cat, u), d = gimme(Dog, u);
	if(c == d) diffcat(par[0][u], 1, 0);
	if(c< d) diffcat(par[0][u], d-c-1+2, d-c-1);
	spec(u, 1e9);
	return (int) getanswer();
}

int neighbor(int u)
{
	// printf("neigh(%d)\n"s, u);
	ll c = gimme(Cat, u), d = gimme(Dog, u);
	if(stat[u] == 1)
	{
		if(c == d) diffcat(par[0][u], 0, -1);
		if(c> d) diffcat(par[0][u], -(c-d-1), -(c-d-1+2));
	}
	if(stat[u] == 2)
	{
		if(c == d) diffcat(par[0][u], -1, 0);
		if(c< d) diffcat(par[0][u], -(d-c-1+2), -(d-c-1));
	}
	stat[u] = 0;
	spec(u, c-d);
	return (int) getanswer();
}

void initialize(int N, vector<int> A, vector<int> B)
{
	n = N;
	for(int i = 0; i< n; i++)
	{
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}
	dfs(); hld();
	foo.build();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 27896 KB Output is correct
2 Correct 48 ms 27896 KB Output is correct
3 Correct 40 ms 27896 KB Output is correct
4 Correct 40 ms 27896 KB Output is correct
5 Correct 41 ms 27768 KB Output is correct
6 Correct 42 ms 27896 KB Output is correct
7 Correct 40 ms 27900 KB Output is correct
8 Correct 41 ms 27932 KB Output is correct
9 Correct 41 ms 27840 KB Output is correct
10 Correct 41 ms 27896 KB Output is correct
11 Correct 40 ms 27896 KB Output is correct
12 Correct 40 ms 27896 KB Output is correct
13 Correct 40 ms 27896 KB Output is correct
14 Correct 40 ms 27896 KB Output is correct
15 Correct 40 ms 27768 KB Output is correct
16 Correct 41 ms 28024 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 27896 KB Output is correct
2 Correct 48 ms 27896 KB Output is correct
3 Correct 40 ms 27896 KB Output is correct
4 Correct 40 ms 27896 KB Output is correct
5 Correct 41 ms 27768 KB Output is correct
6 Correct 42 ms 27896 KB Output is correct
7 Correct 40 ms 27900 KB Output is correct
8 Correct 41 ms 27932 KB Output is correct
9 Correct 41 ms 27840 KB Output is correct
10 Correct 41 ms 27896 KB Output is correct
11 Correct 40 ms 27896 KB Output is correct
12 Correct 40 ms 27896 KB Output is correct
13 Correct 40 ms 27896 KB Output is correct
14 Correct 40 ms 27896 KB Output is correct
15 Correct 40 ms 27768 KB Output is correct
16 Correct 41 ms 28024 KB Output is correct
17 Correct 74 ms 28152 KB Output is correct
18 Correct 74 ms 28172 KB Output is correct
19 Correct 58 ms 28024 KB Output is correct
20 Correct 42 ms 28000 KB Output is correct
21 Correct 53 ms 27840 KB Output is correct
22 Correct 53 ms 27896 KB Output is correct
23 Correct 80 ms 28024 KB Output is correct
24 Correct 75 ms 27984 KB Output is correct
25 Correct 68 ms 28024 KB Output is correct
26 Correct 52 ms 28024 KB Output is correct
27 Correct 44 ms 27896 KB Output is correct
28 Correct 44 ms 28028 KB Output is correct
29 Correct 55 ms 28152 KB Output is correct
30 Correct 49 ms 27896 KB Output is correct
31 Correct 43 ms 28024 KB Output is correct
32 Correct 53 ms 28024 KB Output is correct

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 27896 KB Output is correct
2 Correct 48 ms 27896 KB Output is correct
3 Correct 40 ms 27896 KB Output is correct
4 Correct 40 ms 27896 KB Output is correct
5 Correct 41 ms 27768 KB Output is correct
6 Correct 42 ms 27896 KB Output is correct
7 Correct 40 ms 27900 KB Output is correct
8 Correct 41 ms 27932 KB Output is correct
9 Correct 41 ms 27840 KB Output is correct
10 Correct 41 ms 27896 KB Output is correct
11 Correct 40 ms 27896 KB Output is correct
12 Correct 40 ms 27896 KB Output is correct
13 Correct 40 ms 27896 KB Output is correct
14 Correct 40 ms 27896 KB Output is correct
15 Correct 40 ms 27768 KB Output is correct
16 Correct 41 ms 28024 KB Output is correct
17 Correct 74 ms 28152 KB Output is correct
18 Correct 74 ms 28172 KB Output is correct
19 Correct 58 ms 28024 KB Output is correct
20 Correct 42 ms 28000 KB Output is correct
21 Correct 53 ms 27840 KB Output is correct
22 Correct 53 ms 27896 KB Output is correct
23 Correct 80 ms 28024 KB Output is correct
24 Correct 75 ms 27984 KB Output is correct
25 Correct 68 ms 28024 KB Output is correct
26 Correct 52 ms 28024 KB Output is correct
27 Correct 44 ms 27896 KB Output is correct
28 Correct 44 ms 28028 KB Output is correct
29 Correct 55 ms 28152 KB Output is correct
30 Correct 49 ms 27896 KB Output is correct
31 Correct 43 ms 28024 KB Output is correct
32 Correct 53 ms 28024 KB Output is correct
33 Execution timed out 3052 ms 36840 KB Time limit exceeded
34 Halted 0 ms 0 KB -