QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#545634 | #1188. Estimating the Flood Risk | BreakPlus | RE | 1ms | 4240kb | C++14 | 1.9kb | 2024-09-03 15:46:59 | 2024-09-03 15:47:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
typedef pair<ll,ll> Pr;
inline ll read(){
ll x=0, f=1; char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
return x*f;
}
const ll dx[4] = {1, 0, 0, -1};
const ll dy[4] = {0, 1, -1, 0};
ll w,d,n,vis[2505],dis[2505],cnt[2505];
ll code(ll i,ll j){ return (i-1)*d+j; }
vector<Pr>E[2505];
ll que[5005],hd,tl;
bool out(ll x,ll y){ return (x<1) || (x>w) || (y<1) || (y>d); }
void solve(){
w=read(), d=read(), n=read();
for(ll i=1;i<=n;i++){
ll x=read(), y=read(), z=read();
E[0].pb(code(x, y), -z);
E[code(x,y)].pb(0, z);
}
for(ll i=1;i<=w;i++){
for(ll j=1;j<=d;j++){
for(ll p=0;p<4;p++){
ll tx = i+dx[p], ty = j+dy[p];
if(out(tx, ty)) continue;
E[code(i,j)].pb(code(tx, ty), 1);
// cout<<"add "<<i<<","<<j<<" to "<<tx<<","<<ty<<endl;
}
}
}
memset(dis,0x3f,sizeof(dis));
que[hd=tl=1]=0; vis[0]=1; dis[0]=0;
while(hd<=tl){
ll x=que[hd++];
vis[x]=0;
// cout<<"now pop "<<x<<" with "<<dis[x]<<endl;
for(auto p: E[x]){
ll y=p.fi, W=p.se;
if(dis[y]>dis[x]+W){
dis[y]=dis[x]+W;
// cout<<"update "<<y<<" as "<<dis[y]<<endl;
cnt[y]=cnt[x]+1;
if(cnt[y]>w*d+1){
// cout<<"node "<<y<<" has "<<cnt[y]<<endl;
// cout<<"w*d+1="<<w*d+1<<endl;
puts("No");
return;
}
if(!vis[y]){
que[++tl]=y;
vis[y]=1;
}
}
}
}
ll ans=0;
for(ll i=1;i<=w*d;i++) {
// cout<<"node "<<i<<" has "<<dis[i]<<endl;
ans-=dis[i];
}
printf("%lld\n", ans);
}
int main(){
#ifdef LOCAL
assert(freopen("input.txt", "r", stdin));
assert(freopen("output.txt", "w", stdout));
#endif
ll T=1;
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3908kb
input:
5 4 2 1 1 10 5 4 3
output:
130
result:
ok "130"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
5 4 3 2 2 0 4 3 0 5 1 2
output:
-14
result:
ok "-14"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
3 3 2 1 1 8 3 3 3
output:
No
result:
ok "No"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
2 2 1 1 1 -100
output:
-404
result:
ok "-404"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
5 4 2 1 1 10 5 4 3
output:
130
result:
ok "130"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
5 4 3 2 2 0 4 3 0 5 1 2
output:
-14
result:
ok "-14"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 3 2 1 1 8 3 3 3
output:
No
result:
ok "No"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
3 3 2 1 1 3 3 3 8
output:
No
result:
ok "No"
Test #9:
score: 0
Accepted
time: 0ms
memory: 4240kb
input:
50 50 50 41 31 23 25 13 -7 9 13 -7 8 46 -14 5 38 -19 31 19 4 35 44 8 21 10 -6 16 26 -7 4 28 -14 33 29 13 2 14 -10 12 34 -9 21 48 -9 6 18 -14 27 28 6 13 7 -6 3 49 -7 14 24 -7 29 16 -1 8 19 -14 30 10 -3 30 15 -1 41 15 9 38 39 12 19 19 -3 4 18 -13 4 42 -14 49 27 15 31 34 10 19 10 -8 10 14 -8 42 43 15 4...
output:
-5997
result:
ok "-5997"
Test #10:
score: 0
Accepted
time: 1ms
memory: 4140kb
input:
50 50 50 21 18 36 39 34 64 29 6 27 26 42 65 8 37 60 26 25 48 22 20 39 21 16 35 48 25 59 1 41 66 34 38 56 36 12 39 3 47 72 6 28 55 42 4 42 46 11 44 9 20 46 5 7 39 50 45 68 32 41 60 1 32 60 25 41 63 1 29 58 16 44 59 40 5 39 29 38 59 43 46 71 49 49 69 25 11 34 4 23 53 38 35 63 1 43 68 28 39 60 1 34 61 ...
output:
122275
result:
ok "122275"
Test #11:
score: -100
Runtime Error
input:
50 50 50 29 19 83 12 42 43 22 42 53 41 28 80 34 3 98 44 38 79 15 11 76 35 10 97 48 50 72 27 45 57 16 16 72 37 8 93 21 18 75 13 43 45 9 43 42 34 42 64 48 47 71 11 31 54 24 45 57 32 14 90 10 35 51 10 13 69 15 42 46 32 12 92 3 12 70 40 23 80 11 40 46 3 18 64 14 14 73 12 32 53 46 49 69 34 29 77 18 21 70...