Submission #128336

#	Time	Username	Problem	Language	Result	Execution time	Memory
128336		eriksuenderhauf	Cats or Dogs (JOI18_catdog)	C++11	0 / 100	7 ms	5880 KiB

catdog

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "catdog.h"
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;

struct tree {
	struct node {
		ll dp[2][2];
	};
	vector<node> seg;
	int sz;

	void merge(int idx) {
		seg[idx].dp[0][0] = seg[idx].dp[0][1] = INF;
		seg[idx].dp[1][0] = seg[idx].dp[1][1] = INF;
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				for (int k = 0; k < 2; k++)
					for (int l = 0; l < 2; l++)
						seg[idx].dp[i][l] = min(seg[idx].dp[i][l], seg[idx*2].dp[i][j] + (j ^ k) + seg[idx*2+1].dp[k][l]);
	}

	void upd(int idx, int l, int r) {
		idx += sz;
		seg[idx].dp[0][0] += l;
		seg[idx].dp[1][1] += r;
		for (idx /= 2; idx > 0; idx /= 2)
			merge(idx);
	}

	void qry(int &l, int &r) {
		l = min(min(seg[1].dp[0][0],seg[1].dp[0][1]), min(seg[1].dp[1][0],seg[1].dp[1][1])+1);
		r = min(min(seg[1].dp[0][0],seg[1].dp[0][1])+1, min(seg[1].dp[1][0],seg[1].dp[1][1]));
	}

	void init(int n) {
		sz = 1; while (sz < n) sz <<= 1;
		seg.resize(sz * 2);
		for (int i = sz; i < 2*sz; i++) {
			seg[i].dp[0][0] = seg[i].dp[1][1] = 0;
			seg[i].dp[1][0] = seg[i].dp[0][1] = INF;
		}
		for (int i = sz-1; i > 0; i--)
			merge(i);
	}
} seg[MAXN];

vi adj[MAXN];
int sz[MAXN], par[MAXN], cnt = 0, len[MAXN], root[MAXN], pos[MAXN];
int n, cur[MAXN], col[MAXN];

int upd(int v, int l, int r) {
	int a = 0, b = 0, c = 0, d = 0;
	while (v != -1) {
		int cur = col[v];
		seg[cur].qry(a, b);
		seg[cur].upd(pos[v], l, r);
		seg[cur].qry(c, d);
		l = c - a;
		r = d - b;
		v = root[cur];
	}
	seg[0].qry(a, b);
	return min(a, b);
}

int getSz(int u, int p) {
	sz[u] = 1;
	par[u] = p;
	for (int v: adj[u])
		if (v != p)
			sz[u] += getSz(v, u);
	return sz[u];
}

void dfs(int u, int p, int cur) {
	col[u] = cur;
	if (len[cur] == 0)
		root[cur] = p;
	pos[u] = len[cur]++;
	pii nx = mp(0, -1);
	for (int v: adj[u])
		if (v != p)
			nx = max(nx, mp(sz[v], v));
	for (int v: adj[u]) {
		if (v == p) continue;
		if (v == nx.se)
			dfs(v, u, cur);
		else
			dfs(v, u, cnt++);
	}
}

void initialize(int N, vi A, vi B) {
	n = N;
	for (int i = 0; i+1 < N; i++) {
		A[i]--, B[i]--;
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}
	getSz(0, -1);
	dfs(0, -1, cnt++);
	for (int i = 0; i < cnt; i++)
		seg[i].init(len[i]);
}

int cat(int v) {
	v--;
	int ret = upd(v, MAXN, 0);
	cur[v] = 1;
	return ret;
}

int dog(int v) {
	v--;
	int ret = upd(v, 0, MAXN);
	cur[v] = 2;
	return ret;
}

int neighbor(int v) {
	v--;
	int ret;
	if (cur[v] == 1)
		upd(v, -MAXN, 0);
	else
		upd(v, 0, -MAXN);
	cur[v] = 0;
	return ret;
}

Compilation message (stderr)

catdog.cpp: In function 'int neighbor(int)':
catdog.cpp:156:9: warning: 'ret' is used uninitialized in this function [-Wuninitialized]
  return ret;
         ^~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62