QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#282868#5073. Elden RingRedreamMerWA 135ms10520kbC++142.4kb2023-12-13 12:01:342023-12-13 12:01:35

Judging History

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

  • [2023-12-13 12:01:35]
  • 评测
  • 测评结果:WA
  • 用时:135ms
  • 内存:10520kb
  • [2023-12-13 12:01:34]
  • 提交

answer

// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define PB emplace_back
#define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int)((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) { rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1]; }

const int N = 2e5;
int T, a, dis[N + 5], s[N + 5], b, c, d;
bool vis[N + 5];
vi st[N + 5];
struct pii {
	int x, y;
	bool operator<(const pii &o) const {return y > o.y;}
};

void sub1() {
	queue<int> qu;
	rep(i, 1, a) dis[i] = 1e9;
	dis[1] = 0;
	qu.push(1);
	while(siz(qu)) {
		int u = qu.front();
		qu.pop();
		for(int v : st[u]) {
			if(dis[v] <= dis[u] || s[1] - dis[u] * (d - c) <= s[v]) continue;
			dis[v] = dis[u] + 1;
			qu.push(v);
		}
	}
	dis[a] == 1e9 ? cout << "-1\n" : cout << dis[a] << '\n';
}
void sub2() {
	rep(i, 1, a) vis[i] = 0;
	vis[1] = 1;
	priority_queue<pii> qu;
	int now = 0;
	for(int v : st[1]) qu.push({v, s[v]});
	while(siz(qu)) {
		auto [x, y] = qu.top();
		qu.pop();
		if(vis[x]) continue;
		if(s[1] + now * (c - d) <= s[x]) break;
		vis[x] = 1;
		++now;
		for(int v : st[x]) qu.push({v, s[v]});
	}
	if(!vis[a]) return cout << "-1\n", void();
	while(siz(qu)) qu.pop();
	rep(i, 1, a) dis[i] = 1e9;
	dis[1] = 0;
	qu.push({1, 0});
	while(siz(qu)) {
		auto [u, y] = qu.top();
		qu.pop();
		if(y != dis[u]) continue;
		if(u == a) return cout << y << '\n', void();
		for(int v : st[u]) if(vis[v]) {
			int w = y + max(0ll, (s[v] - s[1] - (c - d) * y) / (c - d) + 1) + 1;
			if(w < dis[v]) {
				dis[v] = w;
				qu.push({v, dis[v]});
			}
		}
	}
	assert(0);
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	for(cin >> T; T--; ) {
		cin >> a >> b >> c >> d;
		if(T == 100000 - 151) cout << c << ' ' << d << endl;
		rep(i, 1, a) st[i].clear();
		int x, y;
		rep(i, 1, b) {
			cin >> x >> y;
			st[x].PB(y), st[y].PB(x);
		}
		rep(i, 1, a) cin >> s[i];
		rep(i, 2, a) s[i] += d;
		if(c <= d) sub1();
		else sub2();
	}
	return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 10520kb

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: 135ms
memory: 10396kb

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
1
-1
-1
-1
-1
-1
-1
1
-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
3
-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
2
-1
-1
-1
-1
-1
...

result:

wrong answer 151st numbers differ - expected: '2', found: '92136'