| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 551738 | nonsensenonsense1 | Sprinkler (JOI22_sprinkler) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
)
#include <cstdio>
#include <vector>
int md;
inline int mul(int a, int b) {
return (long long)a * b % md;
}
const int N = 200000;
const int LG = 19;
const int K = 500;
std::vector<int> g[N], list[N], t[N];
int q, n, dep[N], pr[N], pos[N], h[N], start[N], out[N], amt;
std::pair<int, int> st[LG][N * 2];
void dfs(int v) {
static int dt = 0;
++dt;
pos[v] = list[dep[v]].size();
list[dep[v]].push_back(v);
start[v] = amt;
st[0][amt++] = std::make_pair(dep[v], v);
for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] != pr[v]) {
st[0][amt++] = std::make_pair(dep[v], v);
pr[g[v][i]] = v;
dep[g[v][i]] = dep[v] + 1;
dfs(g[v][i]);
}
out[v] = dt;
}
int lca(int u, int v) {
u = start[u];
v = start[v];
if (u > v) std::swap(u, v);
++v;
int l = 31 - __builtin_clz(v - u);
return std::min(st[l][u], st[l][v - (1 << l)]).second;
}
int f(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
void update(std::vector<int> &t, int l, int r, int x) {
for (l += t.size() >> 1, r += t.size() >> 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
t[l] = mul(t[l], x);
++l;
}
if (r & 1) {
--r;
t[r] = mul(t[r], x);
}
}
}
int get(std::vector<int> &t, int i) {
int res = 1;
for (i += t.size() >> 1; i > 0; i >>= 1) res = mul(res, t[i]);
return res;
}
int main() {
scanf("%d%d", &n, &md);
for (int i = 1; i < n; ++i) {
int a, b;
scanf("%d%d", &a, &b);
g[a - 1].push_back(b - 1);
g[b - 1].push_back(a - 1);
}
dfs(0);
for (int j = 1; j < LG; ++j) for (int i = 0; i + (1 << j) <= 2 * n; ++i) st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
for (int i = 0; i < n; ++i) scanf("%d", h + i);
for (int i = 0; i < n; ++i) t[i].resize(list[i].size() << 1, 1);
scanf("%d", &q);
while (q--) {
int type, v;
scanf("%d%d", &type, &v);
--v;
if (type == 1) {
int dist, x;
scanf("%d%d", &dist, &x);
for (int i = dep[v] + dist; i >= dep[v] - dist; --i) {
int l = 0, r = list[i].size();
while (l < r) {
int m = l + r >> 1;
if (out[list[i][m]] >= out[v] || f(v, list[i][m]) <= dist) r = m;
else l = m + 1;
}
int fi = r;
l = 0, r = list[i].size();
while (l < r) {
int m = l + r >> 1;
if (out[list[i][m]] >= out[v] && f(v, list[i][m]) > dist) r = m;
else l = m + 1;
}
update(t[i], fi, r, x);
}
} else printf("%d\n", mul(h[v], get(t[dep[v]], pos[v])));
}
return 0;
}
Compilation message (stderr)
sprinkler.cpp:1:1: error: expected unqualified-id before ')' token
1 | )
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:62,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/ext/type_traits.h:162:35: error: 'bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
162 | __is_null_pointer(std::nullptr_t)
| ^
/usr/include/c++/10/ext/type_traits.h:157:5: note: previous declaration 'template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)'
157 | __is_null_pointer(_Type)
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/type_traits.h:162:26: error: 'nullptr_t' is not a member of 'std'
162 | __is_null_pointer(std::nullptr_t)
| ^~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/type_traits:402:26: error: 'std::size_t' has not been declared
402 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/10/type_traits:403:25: error: '_Size' was not declared in this scope
403 | struct is_array<_Tp[_Size]>
| ^~~~~
/usr/include/c++/10/type_traits:403:31: error: template argument 1 is invalid
403 | struct is_array<_Tp[_Size]>
| ^
/usr/include/c++/10/type_traits:508:42: error: 'nullptr_t' is not a member of 'std'
508 | struct __is_null_pointer_helper<std::nullptr_t>
| ^~~~~~~~~
/usr/include/c++/10/type_traits:508:51: error: template argument 1 is invalid
508 | struct __is_null_pointer_helper<std::nullptr_t>
| ^
/usr/include/c++/10/type_traits:1351:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1351 | : public integral_constant<std::size_t, alignof(_Tp)>
| ^~~~~~
In file included from /usr/include/stdio.h:33,
from /usr/include/c++/10/cstdio:42,
from sprinkler.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/type_traits:1351:57: error: template argument 1 is invalid
1351 | : public integral_constant<std::size_t, alignof(_Tp)>
| ^
/usr/include/c++/10/type_traits:1351:57: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1360:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1360 | : public integral_constant<std::size_t, 0> { };
| ^~~~~~
In file included from /usr/include/stdio.h:33,
from /usr/include/c++/10/cstdio:42,
from sprinkler.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/type_traits:1360:46: error: template argument 1 is invalid
1360 | : public integral_constant<std::size_t, 0> { };
| ^
/usr/include/c++/10/type_traits:1360:46: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1362:26: error: 'std::size_t' has not been declared
1362 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/10/type_traits:1363:21: error: '_Size' was not declared in this scope
1363 | struct rank<_Tp[_Size]>
| ^~~~~
/usr/include/c++/10/type_traits:1363:27: error: template argument 1 is invalid
1363 | struct rank<_Tp[_Size]>
| ^
/usr/include/c++/10/type_traits:1364:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1364 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^~~~~~
In file included from /usr/include/stdio.h:33,
from /usr/include/c++/10/cstdio:42,
from sprinkler.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/type_traits:1364:65: error: template argument 1 is invalid
1364 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^
/usr/include/c++/10/type_traits:1364:65: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1368:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1368 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^~~~~~
In file included from /usr/include/stdio.h:33,
from /usr/include/c++/10/cstdio:42,
from sprinkler.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/type_traits:1368:65: error: template argument 1 is invalid
1368 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^
/usr/include/c++/10/type_traits:1368:65: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1373:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1373 | : public integral_constant<std::size_t, 0> { };
| ^~~~~~
In file included from /usr/include/stdio.h:33,
from /usr/include/c++/10/cstdio:42,
from sprinkler.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/type_traits:1373:46: error: template argument 1 is invalid
1373 | : public integral_constant<std::size_t, 0> { };
| ^
/usr/include/c++/10/type_traits:1373:46: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1375:42: error: 'std::size_t' has not been declared
1375 | template<typename _Tp, unsigned _Uint, std::size_t _Size>
| ^~~
/usr/include/c++/10/type_traits:1376:23: error: '_Size' was not declared in this scope
1376 | struct extent<_Tp[_Size], _Uint>
| ^~~~~
/usr/include/c++/10/type_traits:1376:36: error: template argument 1 is invalid
1376 | struct extent<_Tp[_Size], _Uint>
| ^
/usr/include/c++/10/type_traits:1377:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1377 | : public integral_constant<std::size_t,
| ^~~~~~
In file included from /usr/include/stdio.h:33,
from /usr/include/c++/10/cstdio:42,
from sprinkler.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/type_traits:1378:24: error: '_Size' was not declared in this scope
1378 | _Uint == 0 ? _Size : extent<_Tp,
| ^~~~~
/usr/include/c++/10/type_traits:1379:28: error: template argument 1 is invalid
1379 | _Uint - 1>::value>
| ^
/usr/include/c++/10/type_traits:1379:28: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1384:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1384 | : public integral_constant<std::size_t,
| ^~~~~~
In file included from /usr/include/stdio.h:33,
from /usr/include/c++/10/cstdio:42,
from sprinkler.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/type_traits:1386:31: error: template argument 1 is invalid
1386 | _Uint - 1>::value>
| ^
/usr/include/c++/10/type_traits:1386:31: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1975:26: error: 'std::size_t' has not been declared
1975 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/10/type_traits:1976:30: error: '_Size' was not declared in this scope
1976 | struct remove_extent<_Tp[_Size]>
| ^~~~~
/usr/include/c++/10/type_traits:1976:36: error: template argument 1 is invalid
1976 | struct remove_extent<_Tp[_Size]>
| ^
/usr/include/c++/10/type_traits:1988:26: error: 'std::size_t' has not been declared
1988 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/10/type_traits:1989:35: error: '_Size' was not declared in this scope
1989 | struct remove_all_extents<_Tp[_Size]>
| ^~~~~
/usr/include/c++/10/type_traits:1989:41: error: template argument 1 is invalid
1989 | struct remove_all_extents<_Tp[_Size]>
| ^
/usr/include/c++/10/type_traits:2047:12: error: 'std::size_t' has not been declared
2047 | template<std::size_t _Len>
| ^~~
/usr/include/c++/10/type_traits:2052:23: error: '_Len' was not declared in this scope
2052 | unsigned char __data[_Len];
| ^~~~
/usr/include/c++/10/type_traits:2067:12: error: 'std::size_t' has not been declared
2067 | template<std::size_t _Len, std::size_t _Align =
| ^~~
/usr/include/c++/10/type_traits:2067:30: error: 'std::size_t' has not been declared
2067 | template<std::size_t _Len, std::size_t _Align =
| ^~~
/usr/include/c++/10/type_traits:2068:48: error: '_Len' was not declared in this scope
2068 | __alignof__(typename __aligned_storage_msa<_Len>::__type)>
| ^~~~
/usr/include/c++/10/type_traits:2068:52: error: template argument 1 is invalid
2068 | __alignof__(typename __aligned_storage_msa<_Len>::__type)>
| ^
/usr/include/c++/10/type_traits:2073:23: error: '_Len' was not declared in this scope
2073 | unsigned char __data[_Len];
| ^~~~
/usr/include/c++/10/type_traits:2074:37: error: '_Align' was not declared in this scope
2074 | struct __attribute__((__aligned__((_Align)))) { } __align;
| ^~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:92:12: error: 'std::size_t' has not been declared
92 | template<std::size_t...>
| ^~~
/usr/include/c++/10/bits/stl_pair.h:449:36: error: 'std::size_t' has not been declared
449 | template<typename... _Args1, std::size_t... _Indexes1,
| ^~~
/usr/include/c++/10/bits/stl_pair.h:450:36: error: 'std::size_t' has not been declared
450 | typename... _Args2, std::size_t... _Indexes2>
| ^~~
/usr/include/c++/10/bits/stl_pair.h:453:27: error: '_Indexes1' was not declared in this scope
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:453:36: error: expected parameter pack before '...'
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^~~
/usr/include/c++/10/bits/stl_pair.h:453:39: error: template argument 1 is invalid
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^
/usr/include/c++/10/bits/stl_pair.h:453:55: error: '_Indexes2' was not declared in this scope
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:453:64: error: expected parameter pack before '...'
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^~~
/usr/include/c++/10/bits/stl_pair.h:453:67: error: template argument 1 is invalid
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:65,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_iterator_base_types.h:125:67: error: 'ptrdiff_t' does not name a type
125 | template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
| ^~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:65,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_iterator_base_types.h:1:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
+++ |+#include <cstddef>
1 | // Types used in iterator implementation -*- C++ -*-
In file included from /usr/include/c++/10/bits/stl_algobase.h:65,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_iterator_base_types.h:214:15: error: 'ptrdiff_t' does not name a type
214 | typedef ptrdiff_t difference_type;
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_iterator_base_types.h:214:15: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
/usr/include/c++/10/bits/stl_iterator_base_types.h:225:15: error: 'ptrdiff_t' does not name a type
225 | typedef ptrdiff_t difference_type;
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_iterator_base_types.h:225:15: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
In file included from /usr/include/c++/10/bits/stl_algobase.h:66,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_iterator_base_funcs.h:110:5: error: 'ptrdiff_t' does not name a type
110 | ptrdiff_t
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_iterator_base_funcs.h:66:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
65 | #include <debug/assertions.h>
+++ |+#include <cstddef>
66 |
/usr/include/c++/10/bits/stl_iterator_base_funcs.h:116:5: error: 'ptrdiff_t' does not name a type
116 | ptrdiff_t
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_iterator_base_funcs.h:116:5: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
In file included from /usr/include/c++/10/bits/stl_iterator.h:66,
from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/bits/ptr_traits.h:109:20: error: 'ptrdiff_t' was not declared in this scope
109 | = __detected_or_t<ptrdiff_t, __difference_type, _Ptr>;
| ^~~~~~~~~
/usr/include/c++/10/bits/ptr_traits.h:1:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
+++ |+#include <cstddef>
1 | // Pointer Traits -*- C++ -*-
/usr/include/c++/10/bits/ptr_traits.h:109:54: error: template argument 1 is invalid
109 | = __detected_or_t<ptrdiff_t, __difference_type, _Ptr>;
| ^
/usr/include/c++/10/bits/ptr_traits.h:135:15: error: 'ptrdiff_t' does not name a type
135 | typedef ptrdiff_t difference_type;
| ^~~~~~~~~
/usr/include/c++/10/bits/ptr_traits.h:135:15: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
In file included from /usr/include/c++/10/vector:60,
from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_algobase.h: In static member function 'static _Tp* std::__copy_move<_IsMove, true, std::random_access_iterator_tag>::__copy_m(const _Tp*, const _Tp*, _Tp*)':
/usr/include/c++/10/bits/stl_algobase.h:424:10: error: 'ptrdiff_t' does not name a type
424 | const ptrdiff_