Submission #551751

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

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#define se second
#define fi first
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 3;
const int inf = 1 << 30;
int n, A[N], p[N], des[N], d[N], psg[N];
int v[N][2], dp[N][2];
vector<int> G[N], H[N];

int dif(pii a, pii b){
	if(a.se == 0 || b.se == 0) return 0;
	return a.se != b.se;
}

struct CD{
	set<pair<int, int>> s; int ans = 0, top = 0, bot = 0, tp = inf, bp = inf;
	void insert(int v, int cd){
		auto ptr = s.lower_bound({v, cd});
		pii m1 = ptr != s.begin() ? *prev(ptr) : mp(0, 0);
		pii p1 = ptr != s.end() ? *ptr : mp(0, 0);
		ans += dif({v, cd}, m1) + dif({v, cd}, p1) - dif(m1, p1);
		s.insert({v, cd});
		top = s.empty() ? 0 : (s.begin())->se;
		tp = s.empty() ? inf : (s.begin())->fi;
		bot = s.empty() ? 0 : (--s.end())->se;
		bp = s.empty() ? inf : (--s.end())->fi;
	}
	
	void erase(int v){
		auto ptr = s.lower_bound({v, -1});
		pii m1 = ptr != s.begin() ? *prev(ptr) : mp(0, 0);
		pii p1 = ptr != s.end() && next(ptr) != s.end() ? *next(ptr) : mp(0, 0);
		ans += dif(m1, p1) - dif(*ptr, m1) - dif(*ptr, p1);
		s.erase(ptr);
		top = s.empty() ? 0 : (s.begin())->se;
		tp = s.empty() ? inf : (s.begin())->fi;
		bot = s.empty() ? 0 : (--s.end())->se;
		bp = s.empty() ? inf : (--s.end())->fi;
	}
} V[N];

void dfs(int v, int par){
	des[v] = v;
	for(auto i : G[v]){
		if(i != par){
			p[i] = v;
			d[i] = d[v] + 1;
			dfs(i, v);
			des[v] = (G[v].size() - (v != 1) == 1) ? des[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);
//	for(int i = 1; i <= n; i++) des[i] = i;
	map<int, vector<int>> PC;
	for(int i = 1; i <= n; i++){
		PC[des[i]].push_back(i);
	}
//	for(int i = 1; i <= n; i++){
//		cout << des[i] << ' ';
//	}
//	cout << endl;
	for(auto& i : PC){
		sort(i.se.begin(), i.se.end(), [](int a, int b){
			return d[a] < d[b];
		});
	}
	
	vector<int> sg;
	for(auto i : PC){
		sg.pb(i.se[0]);
	}
	for(auto i : sg){
		H[p[i]].pb(des[i]);
		psg[des[i]] = p[i];
	}
}

void lift(int v){
	while(true){
		dp[v][0] = dp[v][1] = 0;
		for(auto i : H[v]){
			dp[v][0] += min(dp[i][0], dp[i][1] + 1);
			dp[v][1] += min(dp[i][1], dp[i][0] + 1);
		}
		// cout << "***" << endl << v << ' ' << dp[v][0] << ' ' << dp[v][1] << endl;
		if(!V[v].s.empty()){
			int res = inf;
			if(V[v].bp == d[v]){
				if(V[v].bot == 1) res = dp[v][0];
				else if(V[v].bot == 2) res = dp[v][1];
			}else{
				if(V[v].bot == 1) res = min(dp[v][0], dp[v][1] + 1);
				else if(V[v].bot == 2) res = min(dp[v][0] + 1, dp[v][1]);
			}
			res += V[v].ans;
			// cout << v << ' ' << dp[v][0] << ' ' << dp[v][1] << endl;
			if(V[v].top == 1){
				dp[v][1] = res + 1;
				dp[v][0] = res;
			}else if(V[v].top == 2){
				dp[v][0] = res + 1;
				dp[v][1] = res;
			}else{
				dp[v][0] = dp[v][1] = res;
			}
		}
		if(v == 0) return;
		// cout << v << ' ' << dp[v][0] << ' ' << dp[v][1] << endl;
		v = psg[v];
	}
}

int sol(){
	return min(dp[0][0], dp[0][1]);
}

void out(char c){
//	cout << c << "<<<" << endl;
//	for(int i = 0; i <= n; i++){
//		cout << dp[i][0] << ' ' << dp[i][1] << endl;
//	}
}

int cat(int v) {
	A[v] = 1;
	V[des[v]].insert(d[v], 1);
	lift(des[v]);
	out('c');
	return sol();
}

int dog(int v) {
	A[v] = 2;
	V[des[v]].insert(d[v], 2);
	lift(des[v]);
	out('d');
	return sol();
}

int neighbor(int v) {
	A[v] = 0;
	V[des[v]].erase(d[v]);
	lift(des[v]);
	out('n');
	return sol();
}

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