Submission #886250

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
886250	2023-12-11T15:54:03 Z	javotaz	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KB

factories

// In the Name of Allah
 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 5e5 + 12, inf = 1e18 + 12;
vector<pii> g[N];
int sz[N], cpar[N], q, n;
ll val[N];
set<pair<int, ll>> cdis[N];
bool mrk[N];

void dfs(int u, int par = -1) {
	sz[u] = 1;
	for (auto i: g[u])
		if (i.first != par && !mrk[i.F]) {
			dfs(i.first, u);
			sz[u] += sz[i.first];
		}
}

int find_centroid(int u, int c, int par = -1) {
	for (auto i: g[u])
		if (!mrk[i.first] && i.F != par && sz[i.F] > (c - 1) / 2)
			return find_centroid(i.first, c, u);
	return u;
}

void fill_cdis(int u, int cent, ll c = 0, int par = -1) {
	cdis[cent].insert({u, c});
	for (auto i: g[u])
		if (!mrk[i.first] && i.F != par)
			fill_cdis(i.first, cent, c + i.second, u);
}

void decompose(int u, int par = -1) {
	dfs(u);
	u = find_centroid(u, sz[u]);
	fill_cdis(u, u);
	cpar[u] = par;
	mrk[u] = true;
	for (auto i: g[u])
		if (!mrk[i.first])
			decompose(i.first, u);
}

void add(int u, int v) {
	if (u == -1)
		return;
	val[u] = min(val[u], cdis[u].lower_bound({v, -1})->second);
	add(cpar[u], v);
}

ll ask(int u, int v) {
	if (u == -1)
		return inf;
	ll tmp = cdis[u].lower_bound({v, -1})->second;
	return min(ask(cpar[u], v), tmp + val[u]);
}

void rem(int u) {
	val[u] = inf;
	if (cpar[u] != -1)
		rem(cpar[u]);
}

void Init(int c, int a[], int b[], int d[]) {
	n = c;
	for (int i = 0; i < n - 1; i++) {
		g[a[i]].pb({b[i], d[i]});
		g[b[i]].pb({a[i], d[i]});
	}
	decompose(0);
	fill(val, val + n, inf);
}

ll Query(int s, int x[], int t, int y[]) {
	for (int i = 0; i < s; i++)
		add(x[i], x[i]);
	ll res = inf;
	for (int i = 0; i < t; i++)
		res = min(res, ask(y[i], y[i]));
	for (int i = 0; i < s; i++)
		rem(x[i]);
	return res;
}

Compilation message

factories.cpp:9:8: error: 'pii' was not declared in this scope
    9 | vector<pii> g[N];
      |        ^~~
factories.cpp:9:11: error: template argument 1 is invalid
    9 | vector<pii> g[N];
      |           ^
factories.cpp:9:11: error: template argument 2 is invalid
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:17:18: error: 'begin' was not declared in this scope
   17 |  for (auto i: g[u])
      |                  ^
factories.cpp:17:18: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from factories.cpp:3:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
factories.cpp:17:18: error: 'end' was not declared in this scope
   17 |  for (auto i: g[u])
      |                  ^
factories.cpp:17:18: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from factories.cpp:3:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:25:18: error: 'begin' was not declared in this scope
   25 |  for (auto i: g[u])
      |                  ^
factories.cpp:25:18: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from factories.cpp:3:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
factories.cpp:25:18: error: 'end' was not declared in this scope
   25 |  for (auto i: g[u])
      |                  ^
factories.cpp:25:18: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from factories.cpp:3:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~
factories.cpp: In function 'void fill_cdis(int, int, ll, int)':
factories.cpp:33:18: error: 'begin' was not declared in this scope
   33 |  for (auto i: g[u])
      |                  ^
factories.cpp:33:18: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from factories.cpp:3:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
factories.cpp:33:18: error: 'end' was not declared in this scope
   33 |  for (auto i: g[u])
      |                  ^
factories.cpp:33:18: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from factories.cpp:3:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~
factories.cpp: In function 'void decompose(int, int)':
factories.cpp:44:18: error: 'begin' was not declared in this scope
   44 |  for (auto i: g[u])
      |                  ^
factories.cpp:44:18: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from factories.cpp:3:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
factories.cpp:44:18: error: 'end' was not declared in this scope
   44 |  for (auto i: g[u])
      |                  ^
factories.cpp:44:18: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from factories.cpp:3:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:72:11: error: request for member 'pb' in 'g[(*(a + ((sizetype)(((long unsigned int)i) * 4))))]', which is of non-class type 'int'
   72 |   g[a[i]].pb({b[i], d[i]});
      |           ^~
factories.cpp:73:11: error: request for member 'pb' in 'g[(*(b + ((sizetype)(((long unsigned int)i) * 4))))]', which is of non-class type 'int'
   73 |   g[b[i]].pb({a[i], d[i]});
      |           ^~