답안 #592429

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
592429 2022-07-09T07:47:21 Z Bobaa Cats or Dogs (JOI18_catdog) C++17
컴파일 오류
0 ms 0 KB
#include "catdog.h"
#include <bits/stdc++.h>
using namespace std; 

const int maxn = 1e5 + 5; 
int n;
vector<int> adj[maxn]; 
int A[maxn]; 
int sz[maxn]; 
int par[maxn]; 

void dfs_sz(int cur, int prv) {
	if (prv) adj[cur].erase(find(adj[cur].begin(), adj[cur].end(), prv)); 
	sz[cur] = 1; 
	par[cur] = prv; 
	for (int nxt : adj[cur]) {
		dfs_sz(nxt, cur); 
		sz[cur] += sz[nxt]; 
	}
	nth_element(adj[cur].begin(), adj[cur].begin(), adj[cur].end(), [&](int i, int j) {
		return sz[i] > sz[j]; 
	}); 
}

int hvypar[maxn]; 
int num[maxn]; 
int pos[maxn]; 

void dfs_hld(int cur, int top) {
	hvypar[cur] = top; 
	pos[cur] = num[top]; 
	num[top]++; 
	bool isfrst = true; 
	for (int nxt : adj[cur]) {
		dfs_hld(nxt, (isfrst ? top : nxt)); 
		isfrst = false; 
	}
}

struct mat {
	int a00, a01, a10, a11; 
	friend mat operator * (const mat& a, const mat& b) {
		mat r; 
		r.a00 = min(a.a00 + b.a00, a.a01 + b.a01); 
		r.a01 = min(a.a00 + b.a01, a.a01 + b.a11); 
		r.a10 = min(a.a10 + b.a00, a.a11 + b.a10); 
		r.a11 = min(a.a10 + b.a01, a.a11 + b.a11); 
		return r; 
	}
};

struct segtree {
	int s; 
	vector<mat> cost; 
	
	segtree() {}
	
	segtree(int n) {
		for (s = 1; s < n; s *= 2) {}
		cost = vector<mat>(2 * s); 
		for (int i = 0; i < 2 * s; i++) cost[i].a01 = cost[i].a10 = 1; 
	}
	
	void upd(int i, int& v0, int& v1) {
		i += s; 
		cost[i].a00 += v0; 
		cost[i].a01 += v0; 
		cost[i].a10 += v1; 
		cost[i].a11 += v1; 
		for (i /= 2; i; i /= 2) cost[i] = cost[2 * i] * cost[2 * i + 1]; 
	}
	
	void eval(int& a0, int& a1) {
		a0 = min(cost[1].a00, cost[1].a01); 
		a1 = min(cost[1].a10, cost[1].a11); 
	}
} seg[maxn]; 

void initialize(int k, vector<int> a, vector<int> b) {
	n = k; 
	for (int i = 0; i < n - 1; i++) {
		adj[a[i]].push_back(b[i]); 
		adj[b[i]].push_back(a[i]); 
	}
	for (int i = 1; i <= n; i++) A[i] = 0; 
	dfs_sz(1, 0); 
	dfs_hld(1, 1); 
	for (int i = 1; i <= n; i++) {
		assert((pos[i] == 0) == (hvypar[i] == i)); 
		if (hvypar[i] == i) seg[i] = segtree(num[i]); 
	}
}

int qry();
 
int cat(int v) {
	A[v] = 1;
	upd(v, 0, N);
	return qry();
}
 
int dog(int v) {
	A[v] = 2;
	upd(v, N, 0);
	return qry();
}
 
int neighbor(int v) {
	if (A[v] == 1) upd(v, 0, -n);
	else if (A[v] == 2) upd(v, -n, 0);
	else assert(false);
	A[v] = 0;
	return qry();
}
 
int query() {
	int a0, a1;
	seg[1].eval(a0, a1);
	return min(a0, a1);
}

Compilation message

catdog.cpp: In function 'int cat(int)':
catdog.cpp:98:12: error: 'N' was not declared in this scope
   98 |  upd(v, 0, N);
      |            ^
catdog.cpp:98:2: error: 'upd' was not declared in this scope
   98 |  upd(v, 0, N);
      |  ^~~
catdog.cpp: In function 'int dog(int)':
catdog.cpp:104:9: error: 'N' was not declared in this scope
  104 |  upd(v, N, 0);
      |         ^
catdog.cpp:104:2: error: 'upd' was not declared in this scope
  104 |  upd(v, N, 0);
      |  ^~~
catdog.cpp: In function 'int neighbor(int)':
catdog.cpp:109:17: error: 'upd' was not declared in this scope
  109 |  if (A[v] == 1) upd(v, 0, -n);
      |                 ^~~
catdog.cpp:110:22: error: 'upd' was not declared in this scope
  110 |  else if (A[v] == 2) upd(v, -n, 0);
      |                      ^~~