제출 #111615

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

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int inf = 1e9;

int n, a[MAXN];
vector<int> gph[MAXN];
int sz[MAXN], chn[MAXN], csz[MAXN], dfn[MAXN], par[MAXN], piv;

int slack[MAXN][3];

vector<int> line_query(int s, int e){
	vector<int> ans(3);
	for(int i = e; i >= s; i--){
		for(int j = 0; j < 3; j++){
			ans[j] += slack[i][j];
		}
		vector<int> nxt(3);
		nxt[0] += min({ans[0] + (a[i] ? inf : 0), ans[1] + 1 + (a[i] == 2 ? inf : 0), ans[2] + 1 + (a[i] == 1 ? inf : 0)});
		nxt[1] += min({ans[0] + (a[i] ? inf : 0), ans[1] + 0 + (a[i] == 2 ? inf : 0), ans[2] + 1 + (a[i] == 1 ? inf : 0)});
		nxt[2] += min({ans[0] + (a[i] ? inf : 0), ans[1] + 1 + (a[i] == 2 ? inf : 0), ans[2] + 0 + (a[i] == 1 ? inf : 0)});
		ans = nxt;
	}
	return ans;
}

void Do(int v, int w){
	vector<int> pth;
	for(int i = v; i; i = par[chn[i]]){
		pth.push_back(i);
	}
	reverse(pth.begin(), pth.end());
	for(auto &i : pth){
		auto queryV = line_query(dfn[chn[i]], dfn[chn[i]] + csz[chn[i]] - 1);
		int parV = par[chn[i]];
		parV = dfn[parV];
		slack[parV][0] -= queryV[0];
		slack[parV][1] -= queryV[1];
		slack[parV][2] -= queryV[2];
	}
	a[dfn[v]] = w;
	reverse(pth.begin(), pth.end());
	for(auto &i : pth){
		auto queryV = line_query(dfn[chn[i]], dfn[chn[i]] + csz[chn[i]] - 1);
		int parV = par[chn[i]];
		parV = dfn[parV];
		slack[parV][0] += queryV[0];
		slack[parV][1] += queryV[1];
		slack[parV][2] += queryV[2];
	}
}

int cat(int v) {
	Do(v, 1);
	return *min_element(slack[0], slack[0] + 3);
}

int dog(int v) {
	Do(v, 2);
	return *min_element(slack[0], slack[0] + 3);
}

int neighbor(int v) {
	Do(v, 0);
	return *min_element(slack[0], slack[0] + 3);
}

void dfs(int x){
	sz[x] = 1;
	for(auto &i : gph[x]){
		gph[i].erase(find(gph[i].begin(), gph[i].end(), x));
		par[i] = x;
		dfs(i);
		sz[x] += sz[i];
	}
	sort(gph[x].begin(), gph[x].end(), [&](const int &a, const int &b){
		return sz[a] > sz[b];
	});
}

void hld(int x){
	dfn[x] = ++piv;
	csz[chn[x]]++;
	if(gph[x].empty()) return;
	chn[gph[x][0]] = chn[x];
	hld(gph[x][0]);
	for(int i=1; i<gph[x].size(); i++){
		chn[gph[x][i]] = gph[x][i];
		hld(gph[x][i]);
		auto q = line_query(dfn[gph[x][i]], dfn[gph[x][i]] + csz[gph[x][i]] - 1);
		slack[dfn[x]][0] += q[0];
		slack[dfn[x]][1] += q[1];
		slack[dfn[x]][2] += q[2];
	}
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
	n = N;
	for(int i=0; i<n-1; i++){
		gph[A[i]].push_back(B[i]);
		gph[B[i]].push_back(A[i]);
	}
	dfs(1);
	chn[1] = 1;
	hld(1);
	auto q = line_query(dfn[1], dfn[1] + csz[1] - 1);
	slack[0][0] = q[0];
	slack[0][1] = q[1];
	slack[0][2] = q[2];
}

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

catdog.cpp: In function 'void hld(int)':
catdog.cpp:88:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<gph[x].size(); i++){
               ~^~~~~~~~~~~~~~

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