QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #731693 | #9569. Subway | TheZone | Compile Error | / | / | C++20 | 8.6kb | 2024-11-10 10:33:15 | 2024-11-10 10:33:15 |
Judging History
This is the latest submission verdict.
- [2024-11-10 10:33:15]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-11-10 10:33:15]
- Submitted
answer
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <set>
#include <queue>
#include <algorithm>
#include <numeric>
#define LOG(FMT...) fprintf(stderr, FMT)
#define eb emplace_back
#define em emplace
using namespace std;
typedef long long LL;
constexpr int N = 400005;
constexpr LL INFLL = 0x3f3f3f3f3f3f3f3fll;
int n, m;
int a[N], b[N];
struct Dat {
int x, y; LL d;
Dat() {}
Dat(int _x, int _y, LL _d) : x(_x), y(_y), d(_d) {}
bool operator < (const Dat &t) const {
return d > t.d;
}
};
priority_queue<Dat> q;
struct Subway {
vector<int> sites, we, ord;
vector<LL> dis;
vector<bool> was;
int size() const {
return (int)sites.size();
}
void prework() {
int cnt;
scanf("%d", &cnt);
// sites, we
sites.resize(cnt);
we.resize(cnt - 1);
for (int i = 0; i < cnt; ++i) {
scanf("%d", &sites[i]);
sites[i] -= 1;
if (i < cnt - 1) {
scanf("%d", &we[i]);
}
}
// dis
dis.resize(cnt);
fill(dis.begin(), dis.end(), INFLL);
// ord
ord.resize(cnt);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y) {
return sites[x] < sites[y];
});
// was
was.resize(cnt);
fill(was.begin(), was.end(), false);
/* for (int x : sites) {
LOG("%d ", x);
}
LOG("\n"); */
}
int rk(int site) const {
int l = 0, r = size(), md;
while (l < r) {
md = l + r >> 1;
if (sites[ord[md]] >= site) {
r = md;
} else {
l = md + 1;
}
}
assert(sites[ord[r]] == site);
return ord[r];
}
int operator[] (int k) const {
assert(0 <= k && k < (int) sites.size());
return sites[k];
}
bool chk(int site) const {
return was[rk(site)];
}
} subw[N];
vector<int> ordA[N];
struct Vec {
int x; LL y;
Vec() {}
Vec(int _x, LL _y) : x(_x), y(_y) {}
LL val(int k) const {
return y + k * (LL)x;
}
LL operator * (const Vec &t) const {
return x * t.y - y * t.x;
}
Vec operator - (const Vec &t) const {
return (Vec){x - t.x, y - t.y};
}
};
LL area(const Vec &a, const Vec &b, const Vec &c) {
return (b - a) * (c - a);
}
void updSite(vector<Vec> &v, int beg, int x, LL y) {
if (v.size() && y == v.back().y && x >= v.back().x) {
return;
}
const Vec &t = Vec(x, y);
while (v.size() > beg + 1 && area(v[v.size() - 2], v.back(), t) >= 0) {
v.pop_back();
}
v.eb(t);
}
vector<Vec> vs[N];
int p[N];
void getSubw(int i, int &k, LL &d) {
vector<int> &t = ordA[i];
while (t.size() && subw[t.back()].chk(i)) {
t.pop_back();
}
if (t.empty()) {
k = -1;
d = -1ll;
return;
}
const vector<Vec> &v = vs[i];
assert((int)v.size() > 0);
// LOG("?? %ld\n", v.size());
k = t.back();
int x = a[k];
while (p[i] + 1 < (int)v.size() && v[p[i] + 1].val(x) <= v[p[i]].val(x)) {
p[i] += 1;
}
d = v[p[i]].val(x);
}
LL dis[N];
void updQ(int x, int y, LL d) {
// LOG("upd: %d, %d, %lld\n", x, y, d);
if (subw[x].dis[y] <= d) {
return;
}
subw[x].dis[y] = d;
q.em(x, y, d);
int site = subw[x][y];
if (d < dis[site]) {
dis[site] = d;
}
}
void transi(int site, int k, LL d) {
updSite(vs[site], p[site], b[k], d);
LL nd;
getSubw(site, k, nd);
if (k == -1) {
return;
}
if (nd < d) {
LOG("??\n");
while (true);
}
updQ(k, subw[k].rk(site), nd);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
scanf("%d", a + i);
}
for (int i = 0; i < m; ++i) {
scanf("%d", b + i);
}
memset(dis, 0x3f, n << 3);
dis[0] = 0ll;
for (int i = 0; i < m; ++i) {
subw[i].prework();
for (int j = 0; j < subw[i].size(); ++j) {
int site = subw[i][j];
// LOG("%d %d %lld\n", i, j, dis[site]);
q.em(i, j, dis[site]);
subw[i].dis[j] = dis[site];
ordA[site].eb(i);
}
}
for (int i = 0; i < n; ++i) {
vector<int> &t = ordA[i];
sort(t.begin(), t.end(), [&](int x, int y) {
return a[x] > a[y];
});
}
while (q.size()) {
auto [x, y, d] = q.top();
// LOG("O: %d %d %d %lld\n", x, y, subw[x][y], d);
q.pop();
if (d != subw[x].dis[y]) {
continue;
}
subw[x].was[y] = true;
int site = subw[x][y];
transi(site, x, d);
if (y + 1 < subw[x].size()) {
updQ(x, y + 1, d + subw[x].we[y]);
}
}
for (int x = 1; x < n; ++x) {
printf("%lld ", dis[x]);
}
puts("");
return 0;
}
/*#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <set>
#include <queue>
#include <algorithm>
#include <numeric>
#define LOG(FMT...) fprintf(stderr, FMT)
#define eb emplace_back
#define em emplace
using namespace std;
typedef long long LL;
constexpr int N = 400005;
constexpr LL INFLL = 0x3f3f3f3f3f3f3f3fll;
int n, m;
int a[N], b[N];
struct Dat {
int x, y; LL d;
Dat() {}
Dat(int _x, int _y, LL _d) : x(_x), y(_y), d(_d) {}
bool operator < (const Dat &t) const {
return d > t.d;
}
};
priority_queue<Dat> q;
struct Subway {
vector<int> sites, we, ord;
vector<LL> dis;
vector<bool> was;
int size() const {
return (int)sites.size();
}
void prework() {
int cnt;
scanf("%d", &cnt);
// sites, we
sites.resize(cnt);
we.resize(cnt - 1);
for (int i = 0; i < cnt; ++i) {
scanf("%d", &sites[i]);
sites[i] -= 1;
if (i < cnt - 1) {
scanf("%d", &we[i]);
}
}
// dis
dis.resize(cnt);
fill(dis.begin(), dis.end(), INFLL);
// ord
ord.resize(cnt);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y) {
return sites[x] < sites[y];
});
// was
was.resize(cnt);
fill(was.begin(), was.end(), false);
/* for (int x : sites) {
LOG("%d ", x);
}
LOG("\n"); */
}
int rk(int site) const {
int l = 0, r = size(), md;
while (l < r) {
md = l + r >> 1;
if (sites[ord[md]] >= site) {
r = md;
} else {
l = md + 1;
}
}
assert(sites[ord[r]] == site);
return ord[r];
}
int operator[] (int k) const {
assert(0 <= k && k < (int) sites.size());
return sites[k];
}
bool chk(int site) const {
return was[rk(site)];
}
} subw[N];
vector<int> ordA[N];
struct Vec {
int x; LL y;
Vec() {}
Vec(int _x, LL _y) : x(_x), y(_y) {}
LL val(int k) const {
return y + k * (LL)x;
}
LL operator * (const Vec &t) const {
return x * t.y - y * t.x;
}
Vec operator - (const Vec &t) const {
return (Vec){x - t.x, y - t.y};
}
};
LL area(const Vec &a, const Vec &b, const Vec &c) {
return (b - a) * (c - a);
}
void updSite(vector<Vec> &v, int beg, int x, LL y) {
if (v.size() && y == v.back().y && x >= v.back().x) {
return;
}
const Vec &t = Vec(x, y);
while (v.size() > beg + 1 && area(v[v.size() - 2], v.back(), t) >= 0) {
v.pop_back();
}
v.eb(t);
}
vector<Vec> vs[N];
int p[N];
void getSubw(int i, int &k, LL &d) {
vector<int> &t = ordA[i];
while (t.size() && subw[t.back()].chk(i)) {
t.pop_back();
}
if (t.empty()) {
k = -1;
d = -1ll;
return;
}
const vector<Vec> &v = vs[i];
assert((int)v.size() > 0);
// LOG("?? %ld\n", v.size());
k = t.back();
int x = a[k];
while (p[i] + 1 < (int)v.size() && v[p[i] + 1].val(x) <= v[p[i]].val(x)) {
p[i] += 1;
}
d = v[p[i]].val(x);
}
LL dis[N];
void updQ(int x, int y, LL d) {
// LOG("upd: %d, %d, %lld\n", x, y, d);
if (subw[x].dis[y] <= d) {
return;
}
subw[x].dis[y] = d;
q.em(x, y, d);
int site = subw[x][y];
if (d < dis[site]) {
dis[site] = d;
}
}
void transi(int site, int k, LL d) {
updSite(vs[site], p[site], b[k], d);
LL nd;
getSubw(site, k, nd);
if (k == -1) {
return;
}
if (nd < d) {
LOG("??\n");
while (true);
}
updQ(k, subw[k].rk(site), nd);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
scanf("%d", a + i);
}
for (int i = 0; i < m; ++i) {
scanf("%d", b + i);
}
memset(dis, 0x3f, n << 3);
dis[0] = 0ll;
for (int i = 0; i < m; ++i) {
subw[i].prework();
for (int j = 0; j < subw[i].size(); ++j) {
int site = subw[i][j];
// LOG("%d %d %lld\n", i, j, dis[site]);
q.em(i, j, dis[site]);
subw[i].dis[j] = dis[site];
ordA[site].eb(i);
}
}
for (int i = 0; i < n; ++i) {
vector<int> &t = ordA[i];
sort(t.begin(), t.end(), [&](int x, int y) {
return a[x] > a[y];
});
}
while (q.size()) {
auto [x, y, d] = q.top();
// LOG("O: %d %d %d %lld\n", x, y, subw[x][y], d);
q.pop();
if (d != subw[x].dis[y]) {
continue;
}
subw[x].was[y] = true;
int site = subw[x][y];
transi(site, x, d);
if (y + 1 < subw[x].size()) {
updQ(x, y + 1, d + subw[x].we[y]);
}
}
for (int x = 1; x < n; ++x) {
printf("%lld ", dis[x]);
}
puts("");
return 0;
}*/
詳細信息
answer.code:295:9: error: expected declaration before ‘}’ token
295 | }
| ^
answer.code:296:26: error: non-member function ‘int rk(int)’ cannot have cv-qualifier
296 | int rk(int site) const {
| ^~~~~
answer.code: In function ‘int rk(int)’:
answer.code:297:36: error: no matching function for call to ‘size()’
297 | int l = 0, r = size(), md;
| ~~~~^~
In file included from /usr/include/c++/13/set:65,
from answer.code:5:
/usr/include/c++/13/bits/range_access.h:264:5: note: candidate: ‘template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)’
264 | size(const _Container& __cont) noexcept(noexcept(__cont.size()))
| ^~~~
/usr/include/c++/13/bits/range_access.h:264:5: note: template argument deduction/substitution failed:
answer.code:297:36: note: candidate expects 1 argument, 0 provided
297 | int l = 0, r = size(), md;
| ~~~~^~
/usr/include/c++/13/bits/range_access.h:274:5: note: candidate: ‘template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])’
274 | size(const _Tp (&)[_Nm]) noexcept
| ^~~~
/usr/include/c++/13/bits/range_access.h:274:5: note: template argument deduction/substitution failed:
answer.code:297:36: note: candidate expects 1 argument, 0 provided
297 | int l = 0, r = size(), md;
| ~~~~^~
answer.code:299:25: error: ‘md’ was not declared in this scope; did you mean ‘m’?
299 | md = l + r >> 1;
| ^~
| m
answer.code:300:29: error: ‘sites’ was not declared in this scope; did you mean ‘site’?
300 | if (sites[ord[md]] >= site) {
| ^~~~~
| site
answer.code:300:35: error: ‘ord’ was not declared in this scope; did you mean ‘ordA’?
300 | if (sites[ord[md]] >= site) {
| ^~~
| ordA
In file included from answer.code:3:
answer.code:306:24: error: ‘sites’ was not declared in this scope; did you mean ‘site’?
306 | assert(sites[ord[r]] == site);
| ^~~~~
answer.code:306:30: error: ‘ord’ was not declared in this scope; did you mean ‘ordA’?
306 | assert(sites[ord[r]] == site);
| ^~~
answer.code: At global scope:
answer.code:309:32: error: non-member function ‘int operator[](int)’ cannot have cv-qualifier
309 | int operator[] (int k) const {
| ^~~~~
answer.code:309:13: error: ‘int operator[](int)’ must be a member function
309 | int operator[] (int k) const {
| ^~~~~~~~
answer.code:313:28: error: non-member function ‘bool chk(int)’ cannot have cv-qualifier
313 | bool chk(int site) const {
| ^~~~~
answer.code: In function ‘bool chk(int)’:
answer.code:314:24: error: ‘was’ was not declared in this scope
314 | return was[rk(site)];
| ^~~
answer.code: At global scope:
answer.code:316:1: error: expected declaration before ‘}’ token
316 | } subw[N];
| ^
answer.code:316:3: error: ‘subw’ does not name a type; did you mean ‘Subway’?
316 | } subw[N];
| ^~~~
| Subway
answer.code:318:13: error: redefinition of ‘std::vector<int> ordA [400005]’
318 | vector<int> ordA[N];
| ^~~~
answer.code:94:13: note: ‘std::vector<int> ordA [400005]’ previously defined here
94 | vector<int> ordA[N];
| ^~~~
answer.code:320:8: error: redefinition of ‘struct Vec’
320 | struct Vec {
| ^~~
answer.code:96:8: note: previous definition of ‘struct Vec’
96 | struct Vec {
| ^~~
answer.code:335:4: error: redefinition of ‘LL area(const Vec&, const Vec&, const Vec&)’
335 | LL area(const Vec &a, const Vec &b, const Vec &c) {
| ^~~~
answer.code:111:4: note: ‘LL area(const Vec&, const Vec&, const Vec&)’ previously defined here
111 | LL area(const Vec &a, const Vec &b, const Vec &c) {
| ^~~~
answer.code:339:6: error: redefinition of ‘void updSite(std::vector<Vec>&, int, int, LL)’
339 | void updSite(vector<Vec> &v, int beg, int x, LL y) {
| ^~~~~~~
answer.code:115:6: note: ‘void updSite(std::vector<Vec>&, int, int, LL)’ previously defined here
115 | void updSite(vector<Vec> &v, int beg, int x, LL y) {
| ^~~~~~~
answer.code:350:13: error: redefinition of ‘std::vector<Vec> vs [400005]’
350 | vector<Vec> vs[N];
| ^~
answer.code:126:13: note: ‘std::vector<Vec> vs [400005]’ previously defined here
126 | vector<Vec> vs[...