oj.uz

Submission #879091

# Submission time Handle Problem Language Result Execution time Memory
879091 2023-11-26T10:34:10 Z serifefedartar Factories (JOI14_factories) C++17
Compilation error
 0 ms 0 KB 
#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], up[LOGN][MAXN], depth[MAXN];
int par[MAXN]
ll depth_dist[MAXN], ans[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 > sz[node])
			return find_centro(u.f, node, n);	
	}
	return node;
}

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

	marked[centro] = true;
	if (q)
		par[centro] = -1;
	else
		par[centro] = node;

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

void dfs(int node, int parent) {
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		depth[u.f] = depth[node] + 1;
		depth_dist[u.f] = depth_dist[node] + u.s;
		up[0][u.f] = node;
		for (int i = 1; i < LOGN; i++)
			up[i][u.f] = up[i-1][up[i-1][u.f]];
		dfs(u.f, node);
	}
}

int find(int node, int k) {
	for (int i = 0; i < LOGN; i++) {
		if ((1<<i) & k)
			node = up[i][node];
	}
	return node;
}

int lca(int a, int b) {
	if (depth[b] > depth[a])
		swap(a, b);
	a = find(a, depth[a] - depth[b]);
	if (a == b)
		return a;

	for (int i = LOGN - 1; i >= 0; i--) {
		if (up[i][a] != up[i][b]) {
			a = up[i][a];
			b = up[i][b];
		}
	}
	return up[0][a];
}

int dist(int a, int b) {
	return depth_dist[a] + depth_dist[b] - 2 * depth_dist[lca(a, b)];
}

void Init(int N, vector<int> A, vector<int> B, vector<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]].push_back({B[i], D[i]});
		graph[B[i]].push_back({A[i], D[i]});
	}
	dfs(1, 1);
	decompose(1, true);

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

void add(int node) {
	int now = node;
	while (now != -1) {
		ans[now] = min(ans[now], dist(now, node));
		now = par[now];
	}
}

void remove(int node) {
	while (node != -1) {
		ans[node] = 1e15;
		node = par[node];
	}
}

ll qry(int node) {
	int now = node;
	ll res = 1e15;
	while (now != -1) {
		res = min(res, dist(now, node) + ans[now]);
		now = par[now];
	}
	return res;
}

ll Query(int S, vector<int> X, int T, vector<int> Y) {
	for (auto u : X)
		add(u);

	ll mn = 1e16;
	for (auto u : Y)
		mn = min(mn, qry(u));

	for (auto u : X)
		remove(u);
	return mn;
}

Compilation message

factories.cpp:16:1: error: expected initializer before 'll'
   16 | ll depth_dist[MAXN], ans[MAXN];
      | ^~
factories.cpp: In function 'void decompose(int, bool)':
factories.cpp:42:3: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   42 |   par[centro] = -1;
      |   ^~~
      |   __pstl::execution::v1::par
In file included from /usr/include/c++/10/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/pstl/execution_defs.h:111:27: note: '__pstl::execution::v1::par' declared here
  111 | constexpr parallel_policy par{};
      |                           ^~~
factories.cpp:44:3: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   44 |   par[centro] = node;
      |   ^~~
      |   __pstl::execution::v1::par
In file included from /usr/include/c++/10/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/pstl/execution_defs.h:111:27: note: '__pstl::execution::v1::par' declared here
  111 | constexpr parallel_policy par{};
      |                           ^~~
factories.cpp:47:14: error: 'parent' was not declared in this scope
   47 |   if (u.f != parent && !marked[u.f])
      |              ^~~~~~
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:57:3: error: 'depth_dist' was not declared in this scope
   57 |   depth_dist[u.f] = depth_dist[node] + u.s;
      |   ^~~~~~~~~~
factories.cpp: In function 'int dist(int, int)':
factories.cpp:90:9: error: 'depth_dist' was not declared in this scope
   90 |  return depth_dist[a] + depth_dist[b] - 2 * depth_dist[lca(a, b)];
      |         ^~~~~~~~~~
factories.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
factories.cpp:103:3: error: 'ans' was not declared in this scope; did you mean 'abs'?
  103 |   ans[i] = 1e15;
      |   ^~~
      |   abs
factories.cpp: In function 'void add(int)':
factories.cpp:109:3: error: 'ans' was not declared in this scope; did you mean 'abs'?
  109 |   ans[now] = min(ans[now], dist(now, node));
      |   ^~~
      |   abs
factories.cpp:110:9: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
  110 |   now = par[now];
      |         ^~~
      |         __pstl::execution::v1::par
In file included from /usr/include/c++/10/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/pstl/execution_defs.h:111:27: note: '__pstl::execution::v1::par' declared here
  111 | constexpr parallel_policy par{};
      |                           ^~~
factories.cpp: In function 'void remove(int)':
factories.cpp:116:3: error: 'ans' was not declared in this scope; did you mean 'abs'?
  116 |   ans[node] = 1e15;
      |   ^~~
      |   abs
factories.cpp:117:10: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
  117 |   node = par[node];
      |          ^~~
      |          __pstl::execution::v1::par
In file included from /usr/include/c++/10/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/pstl/execution_defs.h:111:27: note: '__pstl::execution::v1::par' declared here
  111 | constexpr parallel_policy par{};
      |                           ^~~
factories.cpp: In function 'll qry(int)':
factories.cpp:125:36: error: 'ans' was not declared in this scope; did you mean 'abs'?
  125 |   res = min(res, dist(now, node) + ans[now]);
      |                                    ^~~
      |                                    abs
factories.cpp:126:9: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
  126 |   now = par[now];
      |         ^~~
      |         __pstl::execution::v1::par
In file included from /usr/include/c++/10/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/pstl/execution_defs.h:111:27: note: '__pstl::execution::v1::par' declared here
  111 | constexpr parallel_policy par{};
      |                           ^~~