제출 #61429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61429		qkxwsm	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	15 ms	14456 KiB

catdog

#include <bits/stdc++.h>
#include "catdog.h"

using namespace std;

template<class T>
void readi(T &x)
{
	T input = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		input = input * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		input = -input;
	}
	x = input;
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int aout[20];
	int ilen = 0;
	while(output)
	{
		aout[ilen] = ((output % 10));
		output /= 10;
		ilen++;
	}
	for (int i = ilen - 1; i >= 0; i--)
	{
		putchar(aout[i] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long randomize(long long mod)
{
	return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}

#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-10;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 100013

long long normalize(long long x, long long mod = INF)
{
	return (((x % mod) + mod) % mod);
}

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

int N, K;
vi edge[MAXN];
int id[MAXN];
int parent[MAXN];
int subtree[MAXN];
int heavy[MAXN];
int dp[MAXN][2], wdp[MAXN][2];
vector<int> chains[MAXN];
int ranking[MAXN];
int ans;

struct segtree
{
	vector<int> tree[2][2];
	void update(int w, int L, int R, int idx, int val)
	{

	}
};

segtree seg[MAXN];

void dfs(int u)
{
	subtree[u] = 1;
	for (int v : edge[u])
	{
		if (v == parent[u])
		{
			continue;
		}
		parent[v] = u;
		dfs(v);
		subtree[u] += subtree[v];
	}
	//	cerr << u << ' '  << subtree[u] << endl;
	heavy[u] = -1;
	for (int v : edge[u])
	{
		if (v == parent[u])
		{
			continue;
		}
		if (2 * subtree[v] >= subtree[u])
		{
			heavy[u] = v;
		}
	}
	//	cerr << u << ' ' << heavy[u] << endl;
	return;
}
void dfs_heavy(int u)
{
	for (int v : edge[u])
	{
		if (v == parent[u])
		{
			continue;
		}
		dfs_heavy(v);
	}
	if (heavy[u] == -1)
	{
		int v = u;
		while(v != 0 && heavy[parent[v]] == v)
		{
			//			cerr << v << endl;
			chains[K].PB(v);
			v = parent[v];
		}
		chains[K].PB(v);
		K++;
	}
}
void initialize(int n, vi a, vi b)
{
	//	cout << (1 << (32 - __builtin_clz(11))) << endl;
	N = n;
	for (int i = 0; i < N; i++)
	{
		id[i] = -1;
	}
	for (int i = 0; i < N - 1; i++)
	{
		int u = a[i], v = b[i];
		u--; v--;
		edge[u].PB(v);
		edge[v].PB(u);
	}
	parent[0] = N;
	heavy[N] = 0;
	dfs(0);
	dfs_heavy(0);
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < chains[i].size(); j++)
		{
			ranking[chains[i][j]] = j;
		}
	}
	//	for (int i = 0; i < K; i++)
	//	{
	//		cerr << "chain #" << i << ":";
	//		for (int x : chains[i])
	//		{
	//			cerr << ' ' << x;
	//		}
	//		cerr << endl;
	//	}
}

void work(int u)
{
	if (u != 0)
	{
		int v = parent[u];

	}
}
void solve(int u)
{
	//must have 0...
//	dp[u][0] = 0; dp[u][1] = 0;
//	for (int v : edge[u])
//	{
//		if (v == parent[u])
//		{
//			continue;
//		}
//		dp[u][1] += min(dp[v][1], dp[v][0] + 1);
//		dp[u][0] += min(dp[v][0], dp[v][1] + 1);
//	}
		dp[u][1] = wdp[u][1];
		dp[u][0] = wdp[u][0];
	if (id[u] == 0)
	{
		dp[u][1] = CO;
	}
	if (id[u] == 1)
	{
		dp[u][0] = CO;
	}
	return;
}
void work(int u, int d)
{
	if (u == 0)
	{
		return;
	}
	int v = parent[u];
	if (d == -1)
	{
		work(v, d);
	}
	dp[v][1] += d * min(dp[u][1], dp[u][0] + 1);
	dp[v][0] += d * min(dp[u][0], dp[u][1] + 1);
	if (id[v] == 0)
	{
		dp[v][1] = CO;
	}
	if (id[v] == 1)
	{
		dp[v][0] = CO;
	}
	if (dp[v][1] != CO)
	{
		wdp[v][1] = dp[v][1];
	}
	if (dp[v][0] != CO)
	{
		wdp[v][0] = dp[v][0];
	}
	if (d == 1)
	{
		work(v, d);
	}
}

int go(int u, int val)
{
	id[u] = val;
	work(u, -1);
	solve(u);
	work(u, 1);
	return min(dp[0][1], dp[0][0]);
}

int cat(int u)
{
	u--;
	return go(u, 0);
	//	return 1;
}

int dog(int u)
{
	u--;
	return go(u, 1);
	//	return 2;
}

int neighbor(int u)
{
	u--;
	return go(u, -1);
	//	return 3;
}

컴파일 시 표준 에러 (stderr) 메시지

catdog.cpp: In function 'void initialize(int, vi, vi)':
catdog.cpp:201:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < chains[i].size(); j++)
                   ~~^~~~~~~~~~~~~~~~~~
catdog.cpp: In function 'void work(int)':
catdog.cpp:221:7: warning: unused variable 'v' [-Wunused-variable]
   int v = parent[u];
       ^

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