QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#290225#5073. Elden RingRemakee#WA 159ms10252kbC++202.7kb2023-12-24 16:21:292023-12-24 16:21:29

Judging History

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

  • [2023-12-24 16:21:29]
  • 评测
  • 测评结果:WA
  • 用时:159ms
  • 内存:10252kb
  • [2023-12-24 16:21:29]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

typedef long long LL;

typedef pair<int, int> PII;

#define fi first
#define se second
#define mp make_pair

const int N = 2e5 + 5;

int n, m, A, B, L[N], a[N], b[N], C[N];

vector<int> g[N];

bool chk(int u, int i) {
	return (LL)A * (i - 1) + L[1] > (LL) B * (i) + L[u];
}

const int INF = 0x3f3f3f3f;

int d[N];

priority_queue<PII, vector<PII>, greater<PII> > q;

bool vis[N];

void sv1() {
	for (int i = 1; i <= n; i++) d[i] = INF;
	d[1] = 0;
	q.push(mp(d[1], 1));
	while (!q.empty()) {
		int u = q.top().se; q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int v: g[u]) {
			int T = d[u] + 1;
			if (chk(v, T) && T < d[v]) {
				d[v] = T;
				q.push(mp(d[v], v));
			}
		}
	}
	while (!q.empty()) q.pop();
	int ans = d[n] == INF ? -1 : d[n];
	printf("%d\n", ans);
}


priority_queue<PII> q2;

int now;

void ex(int u) {
	++now;
	for (int v: g[u]) {
		if (!vis[v]) {
			vis[v] = 1;
			q.push(mp(C[v], v));
		}
	}
}

bool inline chk(int K) {
	if (!chk(n, K)) return 0;
	for (int i = 1; i <= n; i++) d[i] = -1;
	d[n] = K;
	q2.push(mp(d[n], n));
	while (!q2.empty()) {
		int u = q2.top().se; q2.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		//cout << u << "....\n";
		for (int v: g[u]) {
			int T = d[u] - 1;
			if (T < 0) continue; 
			if (chk(v, T) && T > d[v]) {
				d[v] = T;
				//cout << v <<"??" << d[v] << endl;
				q2.push(mp(d[v], v));
			}
		}
	}
	for (int i = 1; i <= n; i++) vis[i] = 0; //, cout << d[i] << "???\n";
	while (!q2.empty()) q2.pop();
	now = 0;
	vis[1] = 1;
	ex(1); 

	bool ok = 0;
	while (now <= K) {
		while (!q.empty() && q.top().fi <= now) {
			int u = q.top().se; q.pop();
			q2.push(mp(d[u], u));
		}
		if (q2.empty()) {

			break;
		}
		int u = q2.top().se;
		if (u == n) {
			ok = 1;
			break;
		}
		ex(u);
	}
	for (int i = 1; i <= n; i++) vis[i] = 0;

	return ok;
}

void sv2() {
	for (int i = 1; i <= n; i++) {
		int l = 1, r = n + 1;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (chk(i, mid)) r = mid;
			else l = mid + 1;
		}
		C[i] = r;
	}

	//cout << chk(3); return;
	int l = 1, r = n, ans = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (chk(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n", ans);
}

void clr() {
	for (int i = 1; i <= n; i++) g[i].clear();
}

int main() {
 	int T; scanf("%d", &T);
 	while (T--) {
 		scanf("%d%d%d%d", &n, &m, &A, &B);
 		for (int i = 1; i <= m; i++) {
 			int u, v; scanf("%d%d", &u, &v);
 			g[u].pb(v), g[v].pb(u);
 		}
 		for (int i = 1; i <= n; i++) scanf("%d", L + i);
 		if (A <= B) sv1();
 		else sv2();
 		clr();
 	}
    return 0;
}

詳細信息

Test #1:

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

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: 159ms
memory: 10252kb

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
6
-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
...

result:

wrong answer 59th numbers differ - expected: '3', found: '6'