QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#295647	#5073. Elden Ring	zzuqy^#	WA	250ms	22716kb	C++14	1.9kb	2023-12-31 17:44:26	2023-12-31 17:44:26

Judging History

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

[2023-12-31 17:44:26]
评测

测评结果：WA
用时：250ms
内存：22716kb

查看

[2023-12-31 17:44:26]
提交

answer

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#define ll long long
#define rep(a,b,c) for(int c=a;c<=b;++c)
#define sc(A) scanf("%d",&A)
#define go(x) for(int i=lin[x];i;i=nex[i])
using namespace std;
const int MAXN = 400010;
int n, A, B, m;
int T, len, t, h;
int d[MAXN], a[MAXN], q[MAXN];
int lin[MAXN], ver[MAXN], nex[MAXN];

inline void add(int x, int y) {
	ver[++len] = y;
	nex[len] = lin[x];
	lin[x] = len;
}

void bfs() {
	h = 0;
	q[t = 1] = 1;
	d[1] = 1;
	while (++h <= t) {
		int x = q[h];
		go(x) {
			int tn = ver[i];
			if (!d[tn] && a[1] + (ll)(d[x] - 1) * A - (ll)B * d[x] > a[tn]) {
				d[tn] = d[x] + 1;
				q[++t] = tn;
			}
		}
	}
}

namespace sub2 {
	vector<int>v[MAXN];
	int hi[MAXN];
	void bfs() {
		a[1] -= A;
		int cnt = 0;
		for (int i = 0; i <= n + 1; i++)
			v[i].clear(), d[i] = 1000000000;
		for (int i = 2; i <= n; i++) {
			hi[i] = max(0, (a[i] - a[1]) / (A - B) + 1);
			if (hi[i] > MAXN)
				hi[i] = MAXN - 1;
			//cout << hi[i] << " ";
		}
		h = 0;
		q[t = 1] = 1;
		d[1] = 1;
		while (++h <= t) {
			cnt++;
			int x = q[h];
			go(x) {
				int tn = ver[i];
				if (d[tn] == 1000000000) {
					if (cnt > hi[tn]) {
						d[tn] = max(d[x] + 1, hi[tn]);
						q[++t] = tn;
					} else
						v[hi[tn]].push_back(tn);
				}
			}
			for (auto tn : v[cnt]) {
				d[tn] = cnt ;
				q[++t] = tn;
			}
		}
	}
}

int main() {
	//freopen("1.in", "r", stdin);
	sc(T);
	while (T--) {
		sc(n);
		sc(m);
		sc(A);
		sc(B);
		len = 0;
		rep(1, n, i) {
			lin[i] = 0;
			d[i] = 0;
		}
		rep(1, m, i) {
			int x, y;
			sc(x);
			sc(y);
			add(x, y);
			add(y, x);
		}
		rep(1, n, i)sc(a[i]);
		if (A <= B) {
			bfs();
			printf("%d\n", d[n] - 1);
		} else {
			sub2::bfs();
			if (d[n] != 1000000000)
				printf("%d\n", d[n]);
			else
				printf("-1\n");
		}
	}
	return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 22284kb

input:

2
5 4 5 8
1 2
1 3
1 4
4 5
15 1 1 1 1
5 4 10 5
1 2
1 3
1 4
4 5
10 4 4 4 19

output:

2
4

result:

ok 2 number(s): "2 4"

Test #2:

score: -100

Wrong Answer

time: 250ms

memory: 22716kb

input:

100000
6 10 107812 105568
6 5
3 6
4 6
4 2
5 1
5 6
4 5
1 3
1 2
2 5
124065 140875 29890 80077 116532 35394
9 10 82107 88302
1 2
2 3
5 3
5 1
1 4
9 6
3 5
8 2
5 6
7 5
22670 3735 33660 92823 139960 89319 83335 158330 117349
6 10 181257 173221
5 3
3 4
3 1
5 1
2 1
3 6
3 1
6 2
3 6
4 3
76902 46253 123092 2661...

output:

-1
-1
-1
2
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4
-1
2
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
-1
...

result:

wrong answer 4th numbers differ - expected: '1', found: '2'