| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 374634 | gratus907 | 문명 (KOI17_civilization) | 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 <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;
const int V = 101010;
struct DSU
{
int par[V], sz[V];
DSU(){init(V);}
void init(int n)
{
for (int i = 0; i<n; i++)
par[i] = i, sz[i] = 1;
}
int find(int x)
{
return x == par[x] ? x : (par[x] = find(par[x]));
}
void unite(int x, int y)
{
int u=find(x), v=find(y);
if(u==v) return;
if(sz[u]>sz[v]) swap(u, v);
sz[v]+=sz[u];
sz[u] = 0;
par[u] = par[v];
}
} D;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
pii civID [2020][2020];
int n, k;
struct civ {
int r, c, id, year;
bool operator<(const civ &o) const
{
return year > o.year;
}
};
bool violated(int r, int c)
{
return not (1 <= r and r <= n and 1 <= c and c <= n);
}
int32_t main()
{
usecppio
cin >> n >> k;
queue<civ> q;
for (int i = 1; i <= k; i++)
{
int r, c; cin >> r >> c;
q.push({r, c, i, 0});
civID[r][c] = {i, 0};
}
while(!q.empty())
{
civ cv = q.front();
int r = cv.r, c = cv.c;
//printf("CIV %lld on %lld %lld year %lld\n",cv.id, r, c, cv.year);
q.pop();
for (int i = 0; i < 4; i++)
{
int nr = r + dr[i], nc = c + dc[i];
if (violated(nr, nc))
continue;
if (civID[nr][nc].first != 0 and civID[nr][nc].second <= cv.year)
D.unite(civID[nr][nc].first, cv.id);
else
{
civID[nr][nc] = {cv.id, cv.year+1};
q.push({nr, nc, cv.id, cv.year+1});
}
}
if (D.sz[D.find(1)] == k)
{
cout << cv.year << '\n';
return 0;
}
}
}
Compilation message (stderr)
civilization.cpp:9:13: error: 'll' was not declared in this scope; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:10:18: note: in expansion of macro 'int'
10 | using pii = pair<int, int>;
| ^~~
civilization.cpp:9:13: error: 'll' was not declared in this scope; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:10:23: note: in expansion of macro 'int'
10 | using pii = pair<int, int>;
| ^~~
civilization.cpp:10:26: error: template argument 1 is invalid
10 | using pii = pair<int, int>;
| ^
civilization.cpp:10:26: error: template argument 2 is invalid
civilization.cpp:9:13: error: 'll' does not name a type; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:12:7: note: in expansion of macro 'int'
12 | const int V = 101010;
| ^~~
civilization.cpp:9:13: error: 'll' does not name a type; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:15:5: note: in expansion of macro 'int'
15 | int par[V], sz[V];
| ^~~
civilization.cpp:9:13: error: 'll' has not been declared
9 | #define int ll
| ^~
civilization.cpp:17:15: note: in expansion of macro 'int'
17 | void init(int n)
| ^~~
civilization.cpp:9:13: error: 'll' does not name a type; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:22:5: note: in expansion of macro 'int'
22 | int find(int x)
| ^~~
civilization.cpp:9:13: error: 'll' has not been declared
9 | #define int ll
| ^~
civilization.cpp:26:16: note: in expansion of macro 'int'
26 | void unite(int x, int y)
| ^~~
civilization.cpp:9:13: error: 'll' has not been declared
9 | #define int ll
| ^~
civilization.cpp:26:23: note: in expansion of macro 'int'
26 | void unite(int x, int y)
| ^~~
civilization.cpp: In constructor 'DSU::DSU()':
civilization.cpp:16:16: error: 'V' was not declared in this scope
16 | DSU(){init(V);}
| ^
civilization.cpp: In member function 'void DSU::init(int)':
civilization.cpp:9:13: error: 'll' was not declared in this scope; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:19:14: note: in expansion of macro 'int'
19 | for (int i = 0; i<n; i++)
| ^~~
civilization.cpp:19:25: error: 'i' was not declared in this scope
19 | for (int i = 0; i<n; i++)
| ^
civilization.cpp:20:13: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
20 | par[i] = i, sz[i] = 1;
| ^~~
| __pstl::execution::v1::par
In file included from /usr/include/c++/9/pstl/glue_algorithm_defs.h:15,
from /usr/include/c++/9/algorithm:71,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from civilization.cpp:1:
/usr/include/c++/9/pstl/execution_defs.h:114:27: note: '__pstl::execution::v1::par' declared here
114 | constexpr parallel_policy par{};
| ^~~
civilization.cpp:20:25: error: 'sz' was not declared in this scope
20 | par[i] = i, sz[i] = 1;
| ^~
civilization.cpp: In member function 'void DSU::unite(int, int)':
civilization.cpp:9:13: error: 'll' was not declared in this scope; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:28:9: note: in expansion of macro 'int'
28 | int u=find(x), v=find(y);
| ^~~
civilization.cpp:29:12: error: 'u' was not declared in this scope
29 | if(u==v) return;
| ^
civilization.cpp:29:15: error: 'v' was not declared in this scope
29 | if(u==v) return;
| ^
civilization.cpp:30:12: error: 'sz' was not declared in this scope
30 | if(sz[u]>sz[v]) swap(u, v);
| ^~
civilization.cpp:30:15: error: 'u' was not declared in this scope
30 | if(sz[u]>sz[v]) swap(u, v);
| ^
civilization.cpp:30:21: error: 'v' was not declared in this scope
30 | if(sz[u]>sz[v]) swap(u, v);
| ^
civilization.cpp:31:9: error: 'sz' was not declared in this scope
31 | sz[v]+=sz[u];
| ^~
civilization.cpp:31:12: error: 'v' was not declared in this scope
31 | sz[v]+=sz[u];
| ^
civilization.cpp:31:19: error: 'u' was not declared in this scope
31 | sz[v]+=sz[u];
| ^
civilization.cpp:33:9: error: 'par' was not declared in this scope; did you mean '__pstl::execution::v1::par'?
33 | par[u] = par[v];
| ^~~
| __pstl::execution::v1::par
In file included from /usr/include/c++/9/pstl/glue_algorithm_defs.h:15,
from /usr/include/c++/9/algorithm:71,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
from civilization.cpp:1:
/usr/include/c++/9/pstl/execution_defs.h:114:27: note: '__pstl::execution::v1::par' declared here
114 | constexpr parallel_policy par{};
| ^~~
civilization.cpp: At global scope:
civilization.cpp:9:13: error: 'll' does not name a type; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:37:1: note: in expansion of macro 'int'
37 | int dr[4] = {0, 0, 1, -1};
| ^~~
civilization.cpp:9:13: error: 'll' does not name a type; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:38:1: note: in expansion of macro 'int'
38 | int dc[4] = {1, -1, 0, 0};
| ^~~
civilization.cpp:39:1: error: 'pii' does not name a type
39 | pii civID [2020][2020];
| ^~~
civilization.cpp:9:13: error: 'll' does not name a type; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:40:1: note: in expansion of macro 'int'
40 | int n, k;
| ^~~
civilization.cpp:9:13: error: 'll' does not name a type; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:43:5: note: in expansion of macro 'int'
43 | int r, c, id, year;
| ^~~
civilization.cpp: In member function 'bool civ::operator<(const civ&) const':
civilization.cpp:46:16: error: 'year' was not declared in this scope
46 | return year > o.year;
| ^~~~
civilization.cpp:46:25: error: 'const struct civ' has no member named 'year'
46 | return year > o.year;
| ^~~~
civilization.cpp: At global scope:
civilization.cpp:9:13: error: 'll' was not declared in this scope; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:50:15: note: in expansion of macro 'int'
50 | bool violated(int r, int c)
| ^~~
civilization.cpp:9:13: error: 'll' was not declared in this scope; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:50:22: note: in expansion of macro 'int'
50 | bool violated(int r, int c)
| ^~~
civilization.cpp:50:27: error: expression list treated as compound expression in initializer [-fpermissive]
50 | bool violated(int r, int c)
| ^
civilization.cpp: In function 'int32_t main()':
civilization.cpp:58:12: error: 'n' was not declared in this scope
58 | cin >> n >> k;
| ^
civilization.cpp:58:17: error: 'k' was not declared in this scope
58 | cin >> n >> k;
| ^
civilization.cpp:9:13: error: 'll' was not declared in this scope; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:60:10: note: in expansion of macro 'int'
60 | for (int i = 1; i <= k; i++)
| ^~~
civilization.cpp:60:21: error: 'i' was not declared in this scope
60 | for (int i = 1; i <= k; i++)
| ^
civilization.cpp:62:13: error: expected ';' before 'r'
62 | int r, c; cin >> r >> c;
| ^
civilization.cpp:62:26: error: 'r' was not declared in this scope
62 | int r, c; cin >> r >> c;
| ^
civilization.cpp:62:31: error: 'c' was not declared in this scope
62 | int r, c; cin >> r >> c;
| ^
civilization.cpp:63:28: error: no matching function for call to 'std::queue<civ>::push(<brace-enclosed initializer list>)'
63 | q.push({r, c, i, 0});
| ^
In file included from /usr/include/c++/9/queue:64,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
from civilization.cpp:1:
/usr/include/c++/9/bits/stl_queue.h:259:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(const value_type&) [with _Tp = civ; _Sequence = std::deque<civ, std::allocator<civ> >; std::queue<_Tp, _Sequence>::value_type = civ]'
259 | push(const value_type& __x)
| ^~~~
/usr/include/c++/9/bits/stl_queue.h:259:30: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const civ&'}
259 | push(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_queue.h:264:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(std::queue<_Tp, _Sequence>::value_type&&) [with _Tp = civ; _Sequence = std::deque<civ, std::allocator<civ> >; std::queue<_Tp, _Sequence>::value_type = civ]'
264 | push(value_type&& __x)
| ^~~~
/usr/include/c++/9/bits/stl_queue.h:264:25: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::queue<civ>::value_type&&' {aka 'civ&&'}
264 | push(value_type&& __x)
| ~~~~~~~~~~~~~^~~
civilization.cpp:64:9: error: 'civID' was not declared in this scope; did you mean 'civ'?
64 | civID[r][c] = {i, 0};
| ^~~~~
| civ
civilization.cpp:9:13: error: 'll' was not declared in this scope; did you mean 'all'?
9 | #define int ll
| ^~
civilization.cpp:69:9: note: in expansion of macro 'int'
69 | int r = cv.r, c = cv.c;
| ^~~
civilization.cpp:72:18: error: expected ';' before 'i'
72 | for (int i = 0; i < 4; i++)
| ^
civilization.cpp:72:25: error: 'i' was not declared in this scope
72 | for (int i = 0; i < 4; i++)
| ^
civilization.cpp:74:17: error: expected ';' before 'nr'
74 | int nr = r + dr[i], nc = c + dc[i];
| ^~
civilization.cpp:75:26: error: 'nr' was not declared in this scope
75 | if (violated(nr, nc))
| ^~
civilization.cpp:75:30: error: 'nc' was not declared in this scope
75 | if (violated(nr, nc))
| ^~
civilization.cpp:75:32: error: 'violated' cannot be used as a function
75 | if (violated(nr, nc))
| ^
civilization.cpp:77:17: error: 'civID' was not declared in this scope; did you mean 'civ'?
77 | if (civID[nr][nc].first != 0 and civID[nr][nc].second <= cv.year)
| ^~~~~
| civ
civilization.cpp:77:23: error: 'nr' was not declared in this scope
77 | if (civID[nr][nc].first != 0 and civID[nr][nc].second <= cv.year)
| ^~
civilization.cpp:77:27: error: 'nc' was not declared in this scope
77 | if (civID[nr][nc].first != 0 and civID[nr][nc].second <= cv.year)
| ^~
civilization.cpp:77:73: error: 'struct civ' has no member named 'year'
77 | if (civID[nr][nc].first != 0 and civID[nr][nc].second <= cv.year)
| ^~~~
civilization.cpp:78:49: error: 'struct civ' has no member named 'id'
78 | D.unite(civID[nr][nc].first, cv.id);
| ^~
civilization.cpp:81:37: error: 'struct civ' has no member named 'id'
81 | civID[nr][nc] = {cv.id, cv.year+1};
| ^~
civilization.cpp:81:44: error: 'struct civ' has no member named 'year'
81 | civID[nr][nc] = {cv.id, cv.year+1};
| ^~~~
civilization.cpp:82:36: error: 'struct civ' has no member named 'id'
82 | q.push({nr, nc, cv.id, cv.year+1});
| ^~
civilization.cpp:82:43: error: 'struct civ' has no member named 'year'
82 | q.push({nr, nc, cv.id, cv.year+1});
| ^~~~
civilization.cpp:82:50: error: no matching function for call to 'std::queue<civ>::push(<brace-enclosed initializer list>)'
82 | q.push({nr, nc, cv.id, cv.year+1});
| ^
In file included from /usr/include/c++/9/queue:64,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
from civilization.cpp:1:
/usr/include/c++/9/bits/stl_queue.h:259:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(const value_type&) [with _Tp = civ; _Sequence = std::deque<civ, std::allocator<civ> >; std::queue<_Tp, _Sequence>::value_type = civ]'
259 | push(const value_type& __x)
| ^~~~
/usr/include/c++/9/bits/stl_queue.h:259:30: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const civ&'}
259 | push(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_queue.h:264:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(std::queue<_Tp, _Sequence>::value_type&&) [with _Tp = civ; _Sequence = std::deque<civ, std::allocator<civ> >; std::queue<_Tp, _Sequence>::value_type = civ]'
264 | push(value_type&& __x)
| ^~~~
/usr/include/c++/9/bits/stl_queue.h:264:25: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::queue<civ>::value_type&&' {aka 'civ&&'}
264 | push(value_type&& __x)
| ~~~~~~~~~~~~~^~~
civilization.cpp:85:15: error: 'struct DSU' has no member named 'sz'
85 | if (D.sz[D.find(1)] == k)
| ^~
civilization.cpp:85:20: error: 'struct DSU' has no member named 'find'
85 | if (D.sz[D.find(1)] == k)
| ^~~~
civilization.cpp:87:24: error: 'struct civ' has no member named 'year'
87 | cout << cv.year << '\n';
| ^~~~