QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#731693#9569. SubwayTheZoneCompile Error//C++208.6kb2024-11-10 10:33:152024-11-10 10:33:15

Judging History

你现在查看的是最新测评结果

  • [2024-11-10 10:33:15]
  • 评测
查看
  • [2024-11-10 10:33:15]
  • 提交

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;
}*/
源文件, 语言: C++20

詳細信息 

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[...
English 繁體中文 简体中文

伺服器時間: 2025-01-21 06:33:49 | 開源專案