제출 #153725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
153725		tutis	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3005 ms	12132 KiB

catdog

/*input
3
1 2 1
2 3 1
3 1 2
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int V[101010], C[101010], D[101010];
vector<int>adj[101010];
int pa[101010];
void dfs(int i, int p)
{
	auto it = find(adj[i].begin(), adj[i].end(), p);
	if (it != adj[i].end())
		adj[i].erase(it);
	pa[i] = p;
	for (int j : adj[i])
	{
		dfs(j, i);
	}
}
void initialize(int N, vector<int> A, vector<int> B)
{
	for (int i = 0; i < N - 1; i++)
	{
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(1, 1);
}
void recalc(int v)
{
	C[v] = D[v] = 0;
	for (int w : adj[v])
	{
		C[v] += min(C[w], D[w] + 1);
		D[v] += min(D[w], C[w] + 1);
	}
	if (V[v] == -1)
	{
		D[v] = 101010;
	}
	if (V[v] == 1)
	{
		C[v] = 101010;
	}
	if (v != 1)
		recalc(pa[v]);
}
int cat(int v)
{
	V[v] = -1;
	recalc(v);
	return min(C[1], D[1]);
}
int dog(int v)
{
	V[v] = 1;
	recalc(v);
	return min(C[1], D[1]);
}
int neighbor(int v)
{
	V[v] = 0;
	recalc(v);
	return min(C[1], D[1]);
}

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