oj.uz

답안 #111607

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
111607 2019-05-15T16:59:19 Z gs14004 Cats or Dogs (JOI18_catdog) C++17
0 / 100
 5 ms 2688 KB 
#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){
	for(int i = v; chn[i] != 1; i = par[chn[i]]){
		if(par[chn[i]] == 0) break;
		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;
	for(int i = v; chn[i] != 1; i = par[chn[i]]){
		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);
	auto quer = line_query(dfn[1], dfn[1] + csz[1] - 1);
	return *min_element(quer.begin(), quer.end());
}

int dog(int v) {
	Do(v, 2);
	auto quer = line_query(dfn[1], dfn[1] + csz[1] - 1);
	return *min_element(quer.begin(), quer.end());
}

int neighbor(int v) {
	Do(v, 0);
	auto quer = line_query(dfn[1], dfn[1] + csz[1] - 1);
	return *min_element(quer.begin(), quer.end());
}

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);
}

Compilation message

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

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Incorrect 5 ms 2688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Incorrect 5 ms 2688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Incorrect 5 ms 2688 KB Output isn't correct
4 Halted 0 ms 0 KB -