QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#789090 | #5073. Elden Ring | Moloch | WA | 163ms | 19324kb | C++14 | 3.0kb | 2024-11-27 19:15:02 | 2024-11-27 19:15:10 |
Judging History
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: 19324kb
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: 163ms
memory: 18328kb
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 "5|10|92136|84815|-1" found