| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 540708 | Berted | Port Facility (JOI17_port_facility) | C++14 | 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.
oj.uz
SUBMISSION #540431
# Submission timeUTC+8 Handle Problem Language Result Execution time Memory
540431 2022-03-20 18:42:41 Berted Port Facility (JOI17_port_facility) C++14
0 / 100
14 ms 23796 KB
port_facility
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int MD = 1e9 + 7;
int T, N, cnt, A[2000001], par[1000001], pos[1000001];
vector<int> mem[1000001];
int color[1000001] = {}, mx[1000001][2][2];
set<int> S;
int find(int x) {return (x == par[x]) ? x : find(par[x]);}
inline bool join(int a, int b) {
int ka = color[a], kb = color[b];
//cerr << "JOIN: " << a << " " << b << " called\n";
a = find(a), b = find(b);
if (a == b) return ka != kb;
else {
cnt--;
if (mem[a].size() < mem[b].size()) swap(a, b);
par[b] = a;
while (mem[b].size()) {
mem[a].push_back(mem[b].back());
color[mem[b].back()] ^= (ka == kb);
mem[b].pop_back();
}
for (int i = 0; i < 2; i++) {
vector<int> temp = {mx[a][i][0], mx[a][i][1], mx[b][i ^ (ka == kb)][0], mx[b][i ^ (ka == kb)][1]};
sort(temp.begin(), temp.end());
mx[a][i][0] = temp[3];
mx[a][i][1] = temp[2];
}
//cerr << b << " now rooted to " << a << "\n";
return 1;
}
}
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
bool yes = true;
cin >> N;
cnt = N;
S.clear();
for (int i = 0; i < N; i++) {
pos[i] = -1;
par[i] = i;
color[i] = 0;
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++) mx[i][j][k] = -1;
mem[i] = {i};
}
for (int i = 0; i < N; i++) {
int a, b; cin >> a >> b;
A[a - 1] = i; A[b - 1] = i;
//cerr << i << ": " << a << " " << b << "\n";
}
for (int i = 0; i < 2 * N && yes; i++) {
int u; u = A[i];
if (pos[u] == -1) {
//cerr << "IS: " << i << "\n";
S.insert(i);
pos[u] = i;
} else if (pos[u] != -2) {
auto it = S.upper_bound(pos[u]);
while (it != S.end()) {
int v = *it, vv = A[v];
yes &= join(vv, u);
//cerr << "Check: " << vv << " " << v << " " << find(vv) << " " << color[vv] << "\n";
if (false) it = S.erase(it);
else {it++;}
}
S.erase(pos[u]);
pos[u] = -2;
}
mx[find(u)][color[u]][1] = mx[find(u)][color[u]][0];
mx[find(u)][color[u]][0] = i;
}
if (yes) {
int res = 1;
for (int i = 0; i < cnt; i++) {
res = res << 1;
if (res >= MD) res -= MD;
}
cout << res << "\n";
} else {cout << "0\n";}
return 0;
}
Compilation message (stderr)
port_facility.cpp:2:12: error: stray '#' in program
2 | SUBMISSION #540431
| ^
port_facility.cpp:3:3: error: invalid preprocessing directive #Submission
3 | # Submission timeUTC+8 Handle Problem Language Result Execution time Memory
| ^~~~~~~~~~
port_facility.cpp:84:2: error: extended character is not valid in an identifier
84 | if (false) it = S.erase(it);
| ^
port_facility.cpp:84:5: error: extended character is not valid in an identifier
84 | if (false) it = S.erase(it);
| ^
port_facility.cpp:84:8: error: extended character is not valid in an identifier
84 | if (false) it = S.erase(it);
| ^
port_facility.cpp:84:11: error: extended character is not valid in an identifier
84 | if (false) it = S.erase(it);
| ^
port_facility.cpp:84:14: error: extended character is not valid in an identifier
84 | if (false) it = S.erase(it);
| ^
port_facility.cpp:84:17: error: extended character is not valid in an identifier
84 | if (false) it = S.erase(it);
| ^
port_facility.cpp:84:20: error: extended character is not valid in an identifier
84 | if (false) it = S.erase(it);
| ^
port_facility.cpp:84:23: error: extended character is not valid in an identifier
84 | if (false) it = S.erase(it);
| ^
port_facility.cpp:1:1: error: 'oj' does not name a type
1 | oj.uz
| ^~
In file included from /usr/include/c++/10/iosfwd:40,
from /usr/include/c++/10/ios:38,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/include/c++/10/bits/postypes.h:98:11: error: 'ptrdiff_t' does not name a type
98 | typedef ptrdiff_t streamsize; // Signed integral type
| ^~~~~~~~~
/usr/include/c++/10/bits/postypes.h:41:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
40 | #include <cwchar> // For mbstate_t
+++ |+#include <cstddef>
41 |
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
from /usr/include/c++/10/exception:147,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/include/c++/10/new:126:26: error: declaration of 'operator new' as non-function
126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
| ^~~~~~~~
/usr/include/c++/10/new:126:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
| ^~~~~~
In file included from /usr/include/wchar.h:35,
from /usr/include/c++/10/cwchar:44,
from /usr/include/c++/10/bits/postypes.h:40,
from /usr/include/c++/10/iosfwd:40,
from /usr/include/c++/10/ios:38,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/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/exception_ptr.h:40,
from /usr/include/c++/10/exception:147,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/include/c++/10/new:127:41: error: attributes after parenthesized initializer ignored [-fpermissive]
127 | __attribute__((__externally_visible__));
| ^
/usr/include/c++/10/new:128:26: error: declaration of 'operator new []' as non-function
128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
| ^~~~~~~~
/usr/include/c++/10/new:128:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
| ^~~~~~
In file included from /usr/include/wchar.h:35,
from /usr/include/c++/10/cwchar:44,
from /usr/include/c++/10/bits/postypes.h:40,
from /usr/include/c++/10/iosfwd:40,
from /usr/include/c++/10/ios:38,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/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/exception_ptr.h:40,
from /usr/include/c++/10/exception:147,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/include/c++/10/new:129:41: error: attributes after parenthesized initializer ignored [-fpermissive]
129 | __attribute__((__externally_visible__));
| ^
/usr/include/c++/10/new:135:34: error: 'std::size_t' has not been declared
135 | void operator delete(void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~
/usr/include/c++/10/new:137:36: error: 'std::size_t' has not been declared
137 | void operator delete[](void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~
/usr/include/c++/10/new:140:26: error: declaration of 'operator new' as non-function
140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~~~
/usr/include/c++/10/new:140:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~
In file included from /usr/include/wchar.h:35,
from /usr/include/c++/10/cwchar:44,
from /usr/include/c++/10/bits/postypes.h:40,
from /usr/include/c++/10/iosfwd:40,
from /usr/include/c++/10/ios:38,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/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/exception_ptr.h:40,
from /usr/include/c++/10/exception:147,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/include/c++/10/new:140:52: error: expected primary-expression before 'const'
140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~
/usr/include/c++/10/new:142:26: error: declaration of 'operator new []' as non-function
142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~~~
/usr/include/c++/10/new:142:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~
In file included from /usr/include/wchar.h:35,
from /usr/include/c++/10/cwchar:44,
from /usr/include/c++/10/bits/postypes.h:40,
from /usr/include/c++/10/iosfwd:40,
from /usr/include/c++/10/ios:38,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/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/exception_ptr.h:40,
from /usr/include/c++/10/exception:147,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/include/c++/10/new:142:54: error: expected primary-expression before 'const'
142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~
/usr/include/c++/10/new:174:33: error: declaration of 'operator new' as non-function
174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~~~
/usr/include/c++/10/new:174:51: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~
In file included from /usr/include/wchar.h:35,
from /usr/include/c++/10/cwchar:44,
from /usr/include/c++/10/bits/postypes.h:40,
from /usr/include/c++/10/iosfwd:40,
from /usr/include/c++/10/ios:38,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/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/exception_ptr.h:40,
from /usr/include/c++/10/exception:147,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/include/c++/10/new:174:59: error: expected primary-expression before 'void'
174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
| ^~~~
/usr/include/c++/10/new:176:33: error: declaration of 'operator new []' as non-function
176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~~~
/usr/include/c++/10/new:176:53: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~
In file included from /usr/include/wchar.h:35,
from /usr/include/c++/10/cwchar:44,
from /usr/include/c++/10/bits/postypes.h:40,
from /usr/include/c++/10/iosfwd:40,
from /usr/include/c++/10/ios:38,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/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/exception_ptr.h:40,
from /usr/include/c++/10/exception:147,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/include/c++/10/new:176:61: error: expected primary-expression before 'void'
176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
| ^~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/nested_exception.h:40,
from /usr/include/c++/10/exception:148,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/include/c++/10/type_traits:402:31: 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'; did you mean 'nullptr_t'?
508 | struct __is_null_pointer_helper<std::nullptr_t>
| ^~~~~~~~~
In file included from /usr/include/c++/10/bits/cxxabi_init_exception.h:38,
from /usr/include/c++/10/bits/exception_ptr.h:38,
from /usr/include/c++/10/exception:147,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:433:29: note: 'nullptr_t' declared here
433 | typedef decltype(nullptr) nullptr_t;
| ^~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/nested_exception.h:40,
from /usr/include/c++/10/exception:148,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/include/c++/10/type_traits:508:42: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
508 | struct __is_null_pointer_helper<std::nullptr_t>
| ^~~~~~~~~
In file included from /usr/include/c++/10/bits/cxxabi_init_exception.h:38,
from /usr/include/c++/10/bits/exception_ptr.h:38,
from /usr/include/c++/10/exception:147,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:433:29: note: 'nullptr_t' declared here
433 | typedef decltype(nullptr) nullptr_t;
| ^~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/nested_exception.h:40,
from /usr/include/c++/10/exception:148,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/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/wchar.h:35,
from /usr/include/c++/10/cwchar:44,
from /usr/include/c++/10/bits/postypes.h:40,
from /usr/include/c++/10/iosfwd:40,
from /usr/include/c++/10/ios:38,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/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/nested_exception.h:40,
from /usr/include/c++/10/exception:148,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/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/wchar.h:35,
from /usr/include/c++/10/cwchar:44,
from /usr/include/c++/10/bits/postypes.h:40,
from /usr/include/c++/10/iosfwd:40,
from /usr/include/c++/10/ios:38,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/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/nested_exception.h:40,
from /usr/include/c++/10/exception:148,
from /usr/include/c++/10/ios:39,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from port_facility.cpp:8:
/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/wchar.h:35,
from /usr/include/c++/10/cwchar:44,