oj.uz

Submission #889187

# Submission time Handle Problem Language Result Execution time Memory
889187 2023-12-19T06:54:30 Z Onown Factories (JOI14_factories) C++17
Compilation error
 0 ms 0 KB 
#include <bits/stdc++.h>
#include <factories.h>
using namespace std;
typedef long long int
const int N = 5e5 + 55, L = 2e0 + 20, Q = 7e2 + 72, I = 1e18 + 118;
int n, q, h[N], par[N][L], spt[N][L], dis[N];
vector<pair<int, int>> adj[N];

void dfs(int v, int p) {
	for (auto [u, w]: adj[v])
		if (u != p) {
			par[u][0] = v;
			spt[u][0] = w;
			h[u] = h[v] + 1;
			dfs(u, v);
		}
}

int distance(int v, int u) {
	int ans = 0;
	if (h[v] < h[u]) swap(v, u);
	for (int i = 0; i < L; i++)
		if ((1 << i) & (h[v] - h[u])) {
			ans += spt[v][i];
			v = par[v][i];
		}
	if (v == u) return ans;

	for (int i = L - 1; i >= 0; i--)
		if (par[v][i] != par[u][i]) {
			ans += spt[v][i] + spt[u][i];
			v = par[v][i];
			u = par[u][i];
		}
	return ans + spt[v][0] + spt[u][0];
}

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

	dfs(1, 0);
	for (int i = 1; i < L; i++)
		for (int j = 1; j <= n; j++) {
			par[j][i] = par[par[j][i - 1]][i - 1];
			spt[j][i] = spt[j][i - 1] + spt[par[j][i - 1]][i - 1];
		}
	for (int i = 0; i < N; dis[i++] = I);
}

int Query(int S, int X[], int T, int Y[]) {
	if (S < Q) {
		int ans = I;
		for (int i = 0; i < T; i++)
			for (int j = 0; j < S; j++)
				ans = min(ans, distance(Y[i] + 1, X[j] + 1));
		return ans;
	}
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for (int i = 0; i < S; i++) {
		dis[X[i] + 1] = 0;
		pq.push({0, X[i] + 1});
	}
	while (!pq.empty()) {
		int d = pq.top().first, v = pq.top().second; pq.pop();
		if (dis[v] < d) continue;

		for (auto [u, w]: adj[v])
			if (dis[u] > d + w) {
				dis[u] = d + w;
				pq.push({d + w, u});
			}
	}

	int ans = I;
	for (int i = 0; i < T; i++) ans = min(ans, dis[Y[i] + 1]);
	for (int i = 0; i < N; dis[i++] = I);
	return ans;
}

Compilation message

factories.cpp:4:19: error: two or more data types in declaration of 'N'
    4 | typedef long long int
      |                   ^~~
factories.cpp:4:19: error: two or more data types in declaration of 'L'
factories.cpp:4:19: error: two or more data types in declaration of 'Q'
factories.cpp:4:19: error: two or more data types in declaration of 'I'
factories.cpp:6:13: error: 'N' was not declared in this scope
    6 | int n, q, h[N], par[N][L], spt[N][L], dis[N];
      |             ^
factories.cpp:6:21: error: 'N' was not declared in this scope
    6 | int n, q, h[N], par[N][L], spt[N][L], dis[N];
      |                     ^
factories.cpp:6:24: error: 'L' was not declared in this scope
    6 | int n, q, h[N], par[N][L], spt[N][L], dis[N];
      |                        ^
factories.cpp:6:32: error: 'N' was not declared in this scope
    6 | int n, q, h[N], par[N][L], spt[N][L], dis[N];
      |                                ^
factories.cpp:6:35: error: 'L' was not declared in this scope
    6 | int n, q, h[N], par[N][L], spt[N][L], dis[N];
      |                                   ^
factories.cpp:6:43: error: 'N' was not declared in this scope
    6 | int n, q, h[N], par[N][L], spt[N][L], dis[N];
      |                                           ^
factories.cpp:7:28: error: 'N' was not declared in this scope
    7 | vector<pair<int, int>> adj[N];
      |                            ^
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:10:20: error: 'adj' was not declared in this scope
   10 |  for (auto [u, w]: adj[v])
      |                    ^~~
factories.cpp:12:4: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   12 |    par[u][0] = v;
      |    ^~~
      |    __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:13:4: error: 'spt' was not declared in this scope
   13 |    spt[u][0] = w;
      |    ^~~
factories.cpp:14:4: error: 'h' was not declared in this scope
   14 |    h[u] = h[v] + 1;
      |    ^
factories.cpp: In function 'int distance(int, int)':
factories.cpp:21:6: error: 'h' was not declared in this scope
   21 |  if (h[v] < h[u]) swap(v, u);
      |      ^
factories.cpp:22:22: error: 'L' was not declared in this scope
   22 |  for (int i = 0; i < L; i++)
      |                      ^
factories.cpp:23:19: error: 'h' was not declared in this scope
   23 |   if ((1 << i) & (h[v] - h[u])) {
      |                   ^
factories.cpp:24:11: error: 'spt' was not declared in this scope
   24 |    ans += spt[v][i];
      |           ^~~
factories.cpp:25:8: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   25 |    v = par[v][i];
      |        ^~~
      |        __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:29:15: error: 'L' was not declared in this scope
   29 |  for (int i = L - 1; i >= 0; i--)
      |               ^
factories.cpp:30:7: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   30 |   if (par[v][i] != par[u][i]) {
      |       ^~~
      |       __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:31:11: error: 'spt' was not declared in this scope
   31 |    ans += spt[v][i] + spt[u][i];
      |           ^~~
factories.cpp:35:15: error: 'spt' was not declared in this scope
   35 |  return ans + spt[v][0] + spt[u][0];
      |               ^~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:41:3: error: 'adj' was not declared in this scope
   41 |   adj[A[i] + 1].push_back({B[i] + 1, D[i]});
      |   ^~~
factories.cpp:46:22: error: 'L' was not declared in this scope
   46 |  for (int i = 1; i < L; i++)
      |                      ^
factories.cpp:48:4: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
   48 |    par[j][i] = par[par[j][i - 1]][i - 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:49:4: error: 'spt' was not declared in this scope
   49 |    spt[j][i] = spt[j][i - 1] + spt[par[j][i - 1]][i - 1];
      |    ^~~
factories.cpp:51:25: error: 'dis' was not declared in this scope; did you mean 'dfs'?
   51 |  for (int i = 0; i < N; dis[i++] = I);
      |                         ^~~
      |                         dfs
factories.cpp:51:36: error: 'I' was not declared in this scope
   51 |  for (int i = 0; i < N; dis[i++] = I);
      |                                    ^
factories.cpp: At global scope:
factories.cpp:54:5: error: ambiguating new declaration of 'int Query(int, int*, int, int*)'
   54 | int Query(int S, int X[], int T, int Y[]) {
      |     ^~~~~
In file included from factories.cpp:2:
factories.h:5:11: note: old declaration 'long long int Query(int, int*, int, int*)'
    5 | long long Query(int S, int X[], int T, int Y[]);
      |           ^~~~~
factories.cpp: In function 'int Query(int, int*, int, int*)':
factories.cpp:55:10: error: 'Q' was not declared in this scope
   55 |  if (S < Q) {
      |          ^
factories.cpp:56:13: error: 'I' was not declared in this scope
   56 |   int ans = I;
      |             ^
factories.cpp:65:3: error: 'dis' was not declared in this scope; did you mean 'dfs'?
   65 |   dis[X[i] + 1] = 0;
      |   ^~~
      |   dfs
factories.cpp:70:7: error: 'dis' was not declared in this scope; did you mean 'dfs'?
   70 |   if (dis[v] < d) continue;
      |       ^~~
      |       dfs
factories.cpp:72:21: error: 'adj' was not declared in this scope
   72 |   for (auto [u, w]: adj[v])
      |                     ^~~
factories.cpp:73:8: error: 'dis' was not declared in this scope; did you mean 'dfs'?
   73 |    if (dis[u] > d + w) {
      |        ^~~
      |        dfs
factories.cpp:75:23: error: no matching function for call to 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >::push(<brace-enclosed initializer list>)'
   75 |     pq.push({d + w, u});
      |                       ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::pair<int, int>; _Sequence = std::vector<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<int, int>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, int>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::pair<int, int>; _Sequence = std::vector<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<int, int>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >::value_type&&' {aka 'std::pair<int, int>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
factories.cpp:79:12: error: 'I' was not declared in this scope
   79 |  int ans = I;
      |            ^
factories.cpp:80:45: error: 'dis' was not declared in this scope; did you mean 'dfs'?
   80 |  for (int i = 0; i < T; i++) ans = min(ans, dis[Y[i] + 1]);
      |                                             ^~~
      |                                             dfs
factories.cpp:81:22: error: 'N' was not declared in this scope
   81 |  for (int i = 0; i < N; dis[i++] = I);
      |                      ^
factories.cpp:81:25: error: 'dis' was not declared in this scope; did you mean 'dfs'?
   81 |  for (int i = 0; i < N; dis[i++] = I);
      |                         ^~~
      |                         dfs