답안 #153745

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153745 2019-09-15T17:56:40 Z tutis Cats or Dogs (JOI18_catdog) C++17
0 / 100
4 ms 2680 KB
/*input
3
1 2 1
2 3 1
3 1 2
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int V[101010], C[101010], D[101010];
int Sc[101010], Sd[101010];
vector<int>adj[101010];
int pa[101010];
void dfs(int i, int p)
{
	pa[i] = p;
	for (int j : adj[i])
	{
		if (j != p)
			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, 0);
}
int ans = 0;
void recalc(int v)
{
	int c = C[v];
	int d = D[v];
	Sc[pa[v]] -= C[v];
	Sd[pa[v]] -= D[v];
	C[v] = Sc[v];
	D[v] = Sd[v];
	if (V[v] == -1)
	{
		D[v] = C[v] + 1;
	}
	if (V[v] == 1)
	{
		C[v] = D[v] + 1;
	}
	C[v] = min(C[v], D[v] + 1);
	D[v] = min(D[v], C[v] + 1);
	int x = min(C[v], D[v]);
	ans += x;
	C[v] -= x;
	D[v] -= x;
	Sc[pa[v]] += C[v];
	Sd[pa[v]] += D[v];
	if (v != 1 && (C[v] != c || D[v] != d))
		recalc(pa[v]);
}
int cat(int v)
{
	V[v] = -1;
	recalc(v);
	return ans + min(C[1], D[1]);
}
int dog(int v)
{
	V[v] = 1;
	recalc(v);
	return ans + min(C[1], D[1]);
}
int neighbor(int v)
{
	V[v] = 0;
	recalc(v);
	return ans + min(C[1], D[1]);
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -