QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#545634#1188. Estimating the Flood RiskBreakPlusRE 1ms4240kbC++141.9kb2024-09-03 15:46:592024-09-03 15:47:02

Judging History

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

  • [2024-09-03 15:47:02]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:4240kb
  • [2024-09-03 15:46:59]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: