QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#295640#5073. Elden Ringzzuqy#WA 234ms22880kbC++141.8kb2023-12-31 17:28:352023-12-31 17:28:35

Judging History

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

  • [2023-12-31 17:28:35]
  • 评测
  • 测评结果:WA
  • 用时:234ms
  • 内存:22880kb
  • [2023-12-31 17:28:35]
  • 提交

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() {
		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] + B - 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] = d[x] + 1;
						q[++t] = tn;
					} else
						v[hi[tn]].push_back(tn);
				}
			}
			for (auto tn : v[cnt]) {
				d[tn] = cnt + 1;
				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();
			printf("%d\n", d[n]);
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 20616kb

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: 234ms
memory: 22880kb

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:

1000000000
-1
1000000000
2
-1
-1
-1
1000000000
1000000000
-1
2
-1
-1
-1
-1
1000000000
1000000000
1000000000
1000000000
-1
-1
2
1000000000
-1
-1
1000000000
-1
-1
1000000000
1000000000
1000000000
-1
-1
1000000000
1000000000
1000000000
-1
-1
-1
1000000000
1000000000
1000000000
-1
-1
-1
-1
1000000000
10...

result:

wrong answer 1st numbers differ - expected: '-1', found: '1000000000'