답안 #879124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
879124	2023-11-26T12:01:32 Z	serifefedartar	공장들 (JOI14_factories)	C++17	컴파일 오류	0 ms	0 KB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 5e5 + 100;

vector<vector<pair<int,int>>> graph;
int marked[MAXN], sz[MAXN];
ll ans[MAXN];
vector<pair<int,ll>> anc[MAXN];

int get_sz(int node, int parent) {
	sz[node] = 1;
	for (auto u : graph[node]) {
		if (u.f == parent || marked[u.f])
			continue;
		sz[node] += get_sz(u.f, node);
	}
	return sz[node];
}

int find_centro(int node, int parent, int n) {
	for (auto u : graph[node]) {
		if (u.f != parent && !marked[u.f] && sz[u.f] * 2 > n)
			return find_centro(u.f, node, n);	
	}
	return node;
}

void dfs(int node, int parent, int centro, ll dist) {
	for (auto u : graph[node]) {
		if (u.f == parent || marked[u.f]) 
			continue;
		dfs(u.f, node, dist + u.s);
	}
	anc[node].push_back({centro, dist});
}

void decompose(int node, int parent) {
	int n = get_sz(node, node);
	int centro = find_centro(node, node, n);

	marked[centro] = true;
	for (auto u : graph[centro]) {
		if (!marked[u.f])
			dfs(u.f, centro, centro, 0);
	}

	for (auto u : graph[centro]) {
		if (!marked[u.f])
			decompose(u.f, centro);
	}
}

void Init(int N, int A[], int B[], int D[]) {
	graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
	for (int i = 0; i < N-1; i++) {
		graph[A[i] + 1].push_back({B[i] + 1, D[i]});
		graph[B[i] + 1].push_back({A[i] + 1, D[i]});
	}

	for (int i = 0; i < LOGN; i++)
		up[i][1] = 1;
	dfs(1, 1);
	decompose(1, -1);

	for (int i = 0; i < MAXN; i++)
		ans[i] = 1e15;
}

void add(int node) {
	for (auto u : anc[node])
		ans[u.f] = min(ans[u.f], u.s);
}

void remove(int node) {
	for (auto u : anc[node])
		ans[u.f] = 1e15;
}

ll qry(int node) {
	ll res = 1e15;
	for (auto u : anc[node])
		res = min(res, u.s + ans[u.f]);
	return res;
}

ll Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++)
		add(X[i] + 1);

	ll mn = 1e15;
	for (int i = 0; i < T; i++)
		mn = min(mn, qry(Y[i] + 1));

	for (int i = 0; i < S; i++)
		remove(X[i] + 1);
	return mn;
} 

Compilation message

factories.cpp: In function 'void dfs(int, int, int, ll)':
factories.cpp:40:28: error: too few arguments to function 'void dfs(int, int, int, ll)'
   40 |   dfs(u.f, node, dist + u.s);
      |                            ^
factories.cpp:36:6: note: declared here
   36 | void dfs(int node, int parent, int centro, ll dist) {
      |      ^~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:69:3: error: 'up' was not declared in this scope
   69 |   up[i][1] = 1;
      |   ^~
factories.cpp:70:10: error: too few arguments to function 'void dfs(int, int, int, ll)'
   70 |  dfs(1, 1);
      |          ^
factories.cpp:36:6: note: declared here
   36 | void dfs(int node, int parent, int centro, ll dist) {
      |      ^~~