QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#789111#5073. Elden RingMolochWA 169ms19548kbC++143.0kb2024-11-27 19:17:572024-11-27 19:17:57

Judging History

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

  • [2024-11-27 19:17:57]
  • 评测
  • 测评结果:WA
  • 用时:169ms
  • 内存:19548kb
  • [2024-11-27 19:17:57]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <unordered_map>
#include <bitset>

#define int long long
#define LL long long

using namespace std;
char buf[1 << 21], *p1 = buf, *p2 = buf;
char gc()
{
	if(p1 == p2){p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin);}
	return *(p1) ++;
}
LL read()
{
	LL x = 0, s = 1;
	scanf("%lld", &x); return x;
	char ch = gc();
	if(ch < '0' || ch > '9'){s = ch == '-' ? -1 : s; ch = gc();}
	while('0' <= ch && ch <= '9'){x = (x << 1ll) + (x << 3ll) + (ch ^ 48); ch = gc();}
	return x * s;
}

const int N = 2e5 + 10;
const int INF = 1e9 + 10;;

int n, m, ai, bi;
int li[N];
vector<int> e[N];

int dis[N], st[N];
queue<int> q;
void bfs_ls()
{
	int dv = ai - bi;
	dis[1] = 0; st[1] = 1; q.push(1);
	while(q.size())
	{
		int x = q.front(); q.pop();
		for(int y : e[x])
		{
			if(st[y] || li[y] > li[1] + dv * dis[x]){continue;}
			st[y] = 1; dis[y] = min(dis[x] + 1, dis[y]);
			q.push(y);
		}
	}
}

vector<int> po[N];
int cedi(int x, int y){return x % y ? x / y + 1ll : x / y;}//ceil
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII> > he;
void bfs_gr()
{
	int dv = ai - bi;
//	cerr << "DV:" << dv << "\n";
	dis[1] = 0; st[1] = 1; po[0].push_back(1);
	int prs = 0;
	for(int tim = 0; tim <= n; tim ++)
	{
//		cerr << "TIM:" << tim << "=============================\n";
		for(int x : po[tim])
		{
//			cerr << "  P:" << x << "\n";
			for(int y : e[x])
			{
				if(!st[y]){he.push({li[y], y}); st[y] = 1;}
			}
		}
		if(tim){prs += po[tim].size();}
		while(he.size())
		{
			int y = he.top().second, tmp = cedi(li[y] - li[1], dv);
			if(tmp <= prs){dis[y] = max(tim, tmp) + 1; po[dis[y]].push_back(y); he.pop();}
			else{break;}
		}
	}
}

void init()
{
	while(he.size()){he.pop();}
	while(q.size()){q.pop();}
	for(int i = 0; i <= n + 10; i ++)
	{
		dis[i] = INF; st[i] = li[i] = 0;
		e[i].clear(); po[i].clear();
	}
}

string tonum(int x)
{
	if(x == 0){return "0";}
	string res;
	if(x > 9){res += tonum(x / 10);}
	res += x % 10 + '0';
	return res;
}

int qid = 0;
void solve()
{
	string str;
	
	n = read(); m = read(); ai = read(); bi = read();
	
//	if(qid == 151){str += tonum(n) + "|" + tonum(m)+ "|" + tonum(ai) + "|" + tonum(bi) + "|";}
	
	init();
	for(int i = 1; i <= m; i ++)
	{
		int u = read(), v = read(); e[u].push_back(v); e[v].push_back(u);
//		if(qid == 151){str += tonum(u) + "|" + tonum(v) + "|";}
	}
	for(int i = 1; i <= n; i ++)
	{
		li[i] = read();
		if(qid == 151){str += tonum(li[i]) + "|";}
	}
	
	if(qid == 151){cout << str;}
	
//	li[1] --;
	for(int i = 2; i <= n; i ++){li[i] += bi + 1;}//变成小于等于 
	if(ai <= bi){bfs_ls();}
	else{bfs_gr();}
	
	

	if(dis[n] <= n - 1){printf("%lld\n", dis[n]);}
	else{puts("-1");}
}

signed main()
{
	int tii = read();
	for(int z = 1; z <= tii; z ++){qid = z; solve();}
	return 0;
}


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 19548kb

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: 169ms
memory: 18272kb

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 output format Expected integer, but "156937|175422|160333|69247|14532|-1" found