Submission #551604

#	Time	Username	Problem	Language	Result	Execution time	Memory
551604		QwertyPi	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3078 ms	15896 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#define se second
#define fi first
#define pb push_back
using namespace std;

const int N = 1e5 + 3;
const int inf = 1 << 30;
int n, A[N], p[N], anc[N], d[N];
int dp[N][2];
vector<int> G[N];

struct CD{
	void insert(int v, int cd){
		
	}
	void erase(int v){
		
	}
} V[N];
void dfs(int v, int par){
	for(auto i : G[v]){
		if(i != par){
			p[i] = v;
			anc[i] = (G[v].size() - (v != 1) == 1) ? anc[v] : v;
			d[i] = d[v] + 1;
			dfs(i, v);
		}
	}
}

void initialize(int n, vector<int> A, vector<int> B) {
	::n = n;
	for(int i = 0; i < n - 1; i++){
		G[A[i]].pb(B[i]);
		G[B[i]].pb(A[i]);
	}
	dfs(1, -1);
	map<int, vector<int>> PC;
	for(int i = 1; i <= n; i++){
		PC[anc[i]].push_back(i);
	}
	for(auto& i : PC){
		sort(i.se.begin(), i.se.end(), [](int a, int b){
			return d[a] < d[b];
		});
	}
}

void lift(int v){
	while(v != 0){
		dp[v][0] = dp[v][1] = 0; 
		for(auto i : G[v]){
			if(i != p[v]){
				dp[v][0] += min(dp[i][0], dp[i][1] + 1);
				dp[v][1] += min(dp[i][1], dp[i][0] + 1);
			}
		}
		if(A[v] == 1) dp[v][1] = inf;
		else if(A[v] == 2) dp[v][0] = inf;
		v = p[v];
	}
}

int cat(int v) {
	A[v] = 1;
	V[anc[v]].insert(v, 1);
	lift(v);
//	cout << "c<<<" << endl;
//	for(int i = 1; i <= n; i++){
//		cout << dp[i][0] << ' ' << dp[i][1] << endl;
//	}
	return min(dp[1][0], dp[1][1]);
}

int dog(int v) {
	A[v] = 2;
	V[anc[v]].insert(v, 2);
	lift(v);
//	cout << "d<<<" << endl;
//	for(int i = 1; i <= n; i++){
//		cout << dp[i][0] << ' ' << dp[i][1] << endl;
//	}
	return min(dp[1][0], dp[1][1]);
}

int neighbor(int v) {
	A[v] = 0;
	V[anc[v]].erase(v);
	lift(v);
//	cout << "n<<<" << endl;
//	for(int i = 1; i <= n; i++){
//		cout << dp[i][0] << ' ' << dp[i][1] << endl;
//	}
	return min(dp[1][0], dp[1][1]);
}

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